2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Количество подмножеств конечного множества.
Сообщение01.02.2008, 17:05 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Если конечное множество состоит из $n$ элементов, то оно имеет ровно $2^n$ подмножеств.

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

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

 Профиль  
                  
 
 
Сообщение01.02.2008, 19:59 


17/01/08
42
Ну, на скидку могу предложить 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 $

 Профиль  
                  
 
 
Сообщение02.02.2008, 02:16 
Заслуженный участник


19/06/05
486
МГУ
3.
Пусть $M$ - множество из $n$ элементов. Его подмножества могут состоять из нуля, одного, двух, трех, ..., $n$ элементов, причем различных подмножеств из $k$ элементов ровно ${n\choose k}$ (биномиальный коэффициент - число сочетаний из $n$ по $k$). Следовательно, всего подмножеств будет $$\sum_{k=0}^n{n\choose k}=2^n.$$ :D

 Профиль  
                  
 
 
Сообщение08.02.2008, 01:53 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Приведу ещё один вариант.

Для $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$ --- его размерность, то есть мощность базиса. Остаётся лишь заметить, что одноэлементные подмножества образуют базис.

 Профиль  
                  
 
 Re: Количество подмножеств конечного множества.
Сообщение09.05.2008, 15:21 
Заслуженный участник


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

Ограничимся случаем $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.$

 Профиль  
                  
 
 
Сообщение21.07.2008, 12:04 


10/01/07
285
Санкт-Петербург
AGu
По-моему это та же идея, что предложил Попов А.В. в первом пункте.

 Профиль  
                  
 
 
Сообщение21.07.2008, 13:03 
Заслуженный участник


11/05/08
32166
Gordmit писал(а):
3.
Пусть $M$ - множество из $n$ элементов. Его подмножества могут состоять из нуля, одного, двух, трех, ..., $n$ элементов, причем различных подмножеств из $k$ элементов ровно ${n\choose k}$ (биномиальный коэффициент - число сочетаний из $n$ по $k$). Следовательно, всего подмножеств будет $$\sum_{k=0}^n{n\choose k}=2^n.$$ :D

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

Обозначим через $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$.

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

 Профиль  
                  
 
 Re: Количество подмножеств конечного множества.
Сообщение28.06.2012, 15:07 


17/12/10
5
Вот нашёл в сети такое доказательство:

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

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

 Профиль  
                  
 
 Re: Количество подмножеств конечного множества.
Сообщение28.06.2012, 15:51 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group