Количество подмножеств конечного множества.

[Профессор Снэйп]

Если конечное множество состоит из $n$ элементов, то оно имеет ровно $2^n$ подмножеств.

Этот факт хорошо известен. А вот как его доказывать? Существует довольно много различных доказательств. Предлагаю всем желающим в этой теме рассказать про те доказательства, которые им известны. Среди них попадаются довольно забавные. И наверняка я сам знаю далеко не все варианты, бует интересно посмотреть на новые.

P. S. Кстати, неравенство $n < 2^n$, верное для всех натуральных чисел, можно помимо индукции и исследования поведения дифференцируемой функции $f(x) = 2^x$ доказать ссылкой на теорему Кантора. Теорема Кантора гласит, что для любого множества $X$ множество всех его подмножеств $\mathcal{P}(X)$ имеет мощность строго большую, чем мощность $X$. Подставляя вместо $X$ конечное множество из $n$ элементов, получаем требуемое неравенство.

[Попов А.В.]

Ну, на скидку могу предложить 2 доказательства:
1.
Каждому подмножетву $ X \subseteq M $ ставим в соответствие функцию
$ f_X :M \to \{ 0,1\} $, которая ставит в соответсвие каждому элементу из M 1, если он содержится в X, и ноль в обратном случае. Как легко видеть соответствие между множеством таких отображений и $ 2^M $ есть биекция. Значит $ \left| {2^M } \right|$ есть число таких функций, которое равно $ 2^{\left| M \right|} $.

2.
По индукции.
База:
$ \left| {2^\emptyset } \right| = \left| {\left\{ \emptyset \right\}} \right| = 1 = 2^{\left| \emptyset \right|} $
Инд. переход: Пусть $ \left| M \right| = n $. Фиксируем некоторый элемент множества $ m $. Тогда $ 2^M $ можно разбить на множество подмножеств не содержащих $ m $ - $ \rho _1 $ и множество подмножеств содержащих $ m $ - $ \rho _2 $. (очевидно $ \rho _1 \cap \rho _2 = \emptyset $). Легко видеть что между $ \rho _1 $ и $ \rho _2 $ можно установить биекцию, а также то, что $ \rho _1 = 2^{M/\left\{ m \right\}} $. В итоге получаем $ \left| {2^M } \right| = \left| {2^{M/\left\{ m \right\}} } \right| + \left| {2^{M/\left\{ m \right\}} } \right| = 2 \cdot 2^{n - 1} = 2^n $

[Gordmit]

3.
Пусть $M$ - множество из $n$ элементов. Его подмножества могут состоять из нуля, одного, двух, трех, ..., $n$ элементов, причем различных подмножеств из $k$ элементов ровно ${n\choose k}$ (биномиальный коэффициент - число сочетаний из $n$ по $k$). Следовательно, всего подмножеств будет

$$\sum_{k=0}^n{n\choose k}=2^n.$$

[Профессор Снэйп]

Приведу ещё один вариант.

Для $a, b \subseteq X$ через $a+b$ обозначим симметрическую разность этих множеств, то есть множество $(a \setminus b) \cup (b \setminus a)$. Через $0$ обозначаем пустое множество. Под $\mathbb{F}_2$ подразумевается простое поле характеристики $2$, то есть поле, в котором ровно $2$ различных элемента: ноль и единица. Для $\lambda \in \mathbb{F}_2$ и $x \in \mathcal{P}(X)$ пусть $\lambda \cdot x = 0$ при $\lambda = 0$ и $\lambda \cdot x = x$ при $\lambda = 1$.

При так введённых операциях $\mathcal{P}(X)$ оказывается векторным пространством над $\mathbb{F}_2$ (аксиомы проверяются тривиально). Оно изоморфно $\mathbb{F}_2^n$ и содержит $2^n$ элементов, где $n$ --- его размерность, то есть мощность базиса. Остаётся лишь заметить, что одноэлементные подмножества образуют базис.

[AGu]

Помнится, в какой-то школьной комбинаторной книжке я встречал следующее умеренно строгое доказательство (которое вполне может претендовать на лидерство по доступности молодым умам).

Ограничимся случаем $n>0.$ Пусть $X=\{x_1,x_2,\dots,x_n\},$ где $x_i\ne x_j$ при $i\ne j.$ Каждое подмножество $Y\subset X$ однозначно определяется упорядоченным набором ответов "да" или "нет" на вопросы $x_1\in Y?,\ x_2\in Y?,\ \dots,\ x_n\in Y?,$ причем всякий такой набор ответов определяет некоторое подмножество $Y\subset X$ и разные наборы ответов определяют разные подмножества $Y\subset X.$ Следовательно, число подмножеств множества $X$ совпадает с числом упорядоченных наборов ответов на $n$ вопросов. Осталось заметить, что последнее равно
$\underset{n}{\underbrace{2\times 2\times\cdots\times 2}}=2^n.$

[Mikhail Sokolov]

AGu
По-моему это та же идея, что предложил Попов А.В. в первом пункте.

[ewert]

Gordmit писал(а):

3.
Пусть $M$ - множество из $n$ элементов. Его подмножества могут состоять из нуля, одного, двух, трех, ..., $n$ элементов, причем различных подмножеств из $k$ элементов ровно ${n\choose k}$ (биномиальный коэффициент - число сочетаний из $n$ по $k$). Следовательно, всего подмножеств будет

$$\sum_{k=0}^n{n\choose k}=2^n.$$

Вообще-то, конечно, всё в точности наоборот; но уж баловаться -- так баловаться.

Обозначим через $f(k)$ функцию, которая каждому натуральному $k$ ставит в соответствие количество подмножеств какого-либо множества, содержащего $k$ элементов. Определение корректно: если два разных множества содержат одинаковое количество элементов, то между ними существует биекция, но тогда автоматически устанавливается и биекция между их подмножествами. Поэтому значение $f(k)$ не зависит от выбора множества.
Пусть теперь множества $A$ и $B$ не пересекаются, причём $A$ содержит $n$ элементов, $B$ -- $k$ элементов. Рассмотрим множество $C=A\bigcup B$; в нём $(n+k)$ элементов. Между $2^C$ и $2^A\times2^B$ существует естественная биекция, поэтому $\left|2^C\right|=\left|2^A\right|\cdot\left|2^B\right|$. Это означает, что $f(n+k)=f(n)\cdot f(k)\ (\forall n,k\in\mathbb N)$.
Таким образом, $f$ есть показательная функция: $f(k)=a^k$. Как определить параметр $a$? Это -- сложный вопрос; для ответа на него придётся рассмотреть какое-нибудь конкретное множество. Возьмём, например, множество, состоящее из двух предметов -- апельсина и яблока: $\{\text{а},\text{я}\}$. Непосредственным перебором (я лично использовал среду Matlab 7.0) можно убедиться в том, что у этого множества ровно четыре подмножества: $2^{\{\text{а},\text{я}\}}=\big\{\{\text{а},\text{я}\},\,\{\text{а}\},\,\{\text{я}\},\,\{\}\big\}$.
Итак, $f(2)=a^2=4$, откуда $a=\pm2$. Однако $a>0$ (в противном случае для множеств нечётной мощности количество подмножеств оказалось бы отрицательным, что невозможно). Окончательно приходим к выводу, что $f(k)=2^k$.

Как видите, всё не так уж и трудно.

[doom_ne]

Вот нашёл в сети такое доказательство:

Перенумеруем элементы множества А и для каждого подмножества множества А построим последовательность длины n из нулей и единиц по следующему правилу: на k-ом месте пишем 1, если элемент с номером k входит в подмножество , и 0, если элемент с номером k не входит в подмножество.Итак, каждому подмножеству соответствует своя последовательность нулей и единиц.Например, пустому множеству соответствуем последовательность из одних нулей.Числовсех возможных последовательностей длины n, составленных из нулей иединиц, равно, согласно правилу умножения, $2 \cdot2 ... \cdot2$$=$$2^n$.Следовательно, и число всех подмножеств множества А равно $2^n$ .

Но мне не ясно, почему именно 2? Почему берутся именно 0 и 1, это что - тонкая связь с двоичным кодом? Прошу прощения конечно, за глупый вопрос, но всё же, хотелось бы точно понять это обстоятельство.

[Munin]

Можно любые два разных символа. Два - потому что элемент либо входит в подмножество, либо не входит, других вариантов нет.