2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Мощность множества все подмножеств конечного множества
Сообщение22.11.2010, 15:40 
Аватара пользователя
Если мощность множества все подмножеств конечного множества $M$ число $k$, то очевидно, что добавив один элемент к множеству $M$, мы получим множество, имеющее $2k$ подмножеств. Используя этот факт как индукционный шаг, по индукции легко доказывается, что мощность множества все подмножеств конечного множества $2^n$ (если, конечно, в множестве $n$ элементов). Я полез в книги и нашел доказательство, что мощность множества все подмножеств конечного множества $2^n$, только через бином Ньютона. Знает ли кто-нибудь книгу с доказательством по индукции?

 
 
 
 Re: Мощность множества все подмножеств конечного множества
Сообщение22.11.2010, 15:48 
Аватара пользователя
А не проще комбинаторно? Каждый элемент может либо войти, либо не войти в подмножество. Т. е. по правилу умножения, $\underbrace{2\cdot 2\cdots}_{n}=2^n$.

 
 
 
 Re: Мощность множества все подмножеств конечного множества
Сообщение22.11.2010, 15:51 
Аватара пользователя
А зачем книга? Выберем произвольный элемент. Тогда все подмножества развалятся на два равномощных класса - содержащих этот элемент и не содержащих его. Вот Вам и индуктивный переход.

-- Пн ноя 22, 2010 15:52:57 --

Упс, пардон за невнимательность - именно это и предлагалось. Наверняка в какой-нибудь книжке для иллюстрации индукции это приводится.

caxap Просто и то идругое, но вопрос другой - есть или нету?

 
 
 
 Re: Мощность множества все подмножеств конечного множества
Сообщение22.11.2010, 16:01 
Аватара пользователя
bot в сообщении #379060 писал(а):
Наверняка в какой-нибудь книжке для иллюстрации индукции это приводится.

Тут-то и закавыка! В какой?

 
 
 
 Re: Мощность множества все подмножеств конечного множества
Сообщение22.11.2010, 16:18 
Вообще-то стандартно это оформляется так. Любому подмножеству взаимно-однозначно сопоставляется двоичное число. Количество таких чисел, естественно, равно $2^n$ (та же комбинаторика, конечно, но более прозрачная).

 
 
 
 Re: Мощность множества все подмножеств конечного множества
Сообщение22.11.2010, 16:18 
Ф.А. Новиков "Дискретная математика для программистов", с.25

 
 
 
 Re: Мощность множества все подмножеств конечного множества
Сообщение22.11.2010, 16:30 
Аватара пользователя
ewert в сообщении #379072 писал(а):
Вообще-то стандартно это оформляется так. Любому подмножеству взаимно-однозначно сопоставляется двоичное число. Количество таких чисел, естественно, равно $2^n$ (та же комбинаторика, конечно, но более прозрачная).

У множества $M$ есть $k$ подмножеств. Добавили один элемент к множеству $M$. Все старые подмножества остались на месте и добавилось к каждому подмножеству по элементу. Их стало вдвое больше. Это задачка для третьего класса начальной школы. Куда уж более прозрачно?

Niclax в сообщении #379073 писал(а):
Ф.А. Новиков "Дискретная математика для программистов", с.25
Спасибо!

 
 
 
 Re: Мощность множества все подмножеств конечного множества
Сообщение12.06.2020, 16:14 
Виктор Викторов в сообщении #379052 писал(а):
Если мощность множества все подмножеств конечного множества $M$ число $k$, то очевидно, что добавив один элемент к множеству $M$, мы получим множество, имеющее $2k$ подмножеств. Используя этот факт как индукционный шаг, по индукции легко доказывается, что мощность множества все подмножеств конечного множества $2^n$ (если, конечно, в множестве $n$ элементов). Я полез в книги и нашел доказательство, что мощность множества все подмножеств конечного множества $2^n$, только через бином Ньютона. Знает ли кто-нибудь книгу с доказательством по индукции?


вот здесь - http://poivs.tsput.ru/ru/Math/Logic/The ... ts/Boulean

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group