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

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

Если мощность множества все подмножеств конечного множества $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

[Aafeture]

Здравствуйте.
Проверьте, пожалуйста, верно ли я написала доказательство. Я не люблю индукцию и не хочу ее использовать. Нормально так формулировать?

Докажем теорему о том, что число подмножеств в конечном множестве A равно 2 в степени, равной мощности A.
Возьмем множество A. Пусть элемент X принадлежит A. Пусть мощность A равна n.
Уберем элемент X из А и из оставшихся элементов составим множество B. Тогда мощность B равна (n – 1).
Каждое подмножество множества A либо содержит элемент X, либо не содержит. Каждое подмножество множества B не содержит элемент X. Тогда подмножества множества А – это, во-первых, все подмножества множества B, а во-вторых – те, что получаются простым прибавлением элемента X к каждому подмножеству множества B.
Следовательно, общее число подмножеств множества A в два раза больше числа подмножеств множества B.
Если обозначить количество подмножеств множества из n элементов как P(n), то P(n) $=$ 2P(n – 1). Видим, что каждое добавление элемента удваивает число подмножеств.
Возьмем пустое множество, где количество элементов $=$ 0. Очевидно, что количество его подмножеств равно 1: P(0) $=$ 1. Добавим один элемент – количество подмножеств удвоится: P(1) $=$ 2P(0) $=$ 2. Добавим еще элемент – количество подмножеств еще раз удвоится: P(2) $=$ 2P(1) $=$ 4. Добавим n элементов. P(n) $=$ 2 $\cdot$ 2 $\cdot$ 2 (и так n раз) P(0) $=$ $2^n$.

[Ende]

Aafeture
Оформляйте формулы в $\TeX$. В следующий раз тема уедет в Карантин.

[ozheredov]

Aafeture в сообщении #1721427 писал(а):

Если обозначить количество подмножеств множества из n элементов как P(n), то P(n) $=$ 2P(n – 1). Видим, что каждое добавление элемента удваивает число подмножеств.

Aafeture в сообщении #1721427 писал(а):

Я не люблю индукцию и не хочу ее использовать.

Я один усматриваю здесь противоречие? ))

[Null]

Aafeture в сообщении #1721427 писал(а):

и так n раз

Вот тут нужна аксиома индукции или ее аналог. Просто в данном случае этот факт очевиден и доказательство опускают. Это вопрос преподавания или строгости.