Мощность множества все подмножеств конечного множества

[Виктор Викторов]

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

[caxap]

А не проще комбинаторно? Каждый элемент может либо войти, либо не войти в подмножество. Т. е. по правилу умножения, $\underbrace{2\cdot 2\cdots}_{n}=2^n$.

[bot]

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

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

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

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

[Виктор Викторов]

bot в сообщении #379060 писал(а):

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

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

[ewert]

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

[Niclax]

Ф.А. Новиков "Дискретная математика для программистов", с.25

[Виктор Викторов]

ewert в сообщении #379072 писал(а):

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

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

Niclax в сообщении #379073 писал(а):

Ф.А. Новиков "Дискретная математика для программистов", с.25

Спасибо!

[DaddyM]

Виктор Викторов в сообщении #379052 писал(а):

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

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