Множество всех подмножеств

Множество всех подмножеств (булеан, показательное множество) — множество, состоящее из всех подмножеств данного множества $A$ (включая пустое множество и само множество $A$); обозначается ${\mathcal {P}}(A)$ или $2^{A}$ (так как оно соответствует множеству отображений из $A$ в $\{0,1\}$).

Если два множества равномощны, то равномощны и соответствующие множества всех подмножеств. Обратное утверждение (то есть инъективность операции $\kappa \mapsto 2^{\kappa }$ для кардиналов) является независимым от ZFC.

В категории множеств можно снабдить функцию ${\mathcal {P}}$ структурой ковариантного или контравариантного функтора следующим образом:

• ковариантный функтор отображает функцию $f\colon A\to B$ в функцию ${\mathcal {P}}f\colon {\mathcal {P}}A\to {\mathcal {P}}B$ такую, что она отображает $X$ в образ $X$ относительно $f$;
• контравариантный функтор отображает функцию $f\colon A\to B$ в ${\mathcal {P}}f\colon {\mathcal {P}}B\to {\mathcal {P}}A$ такую, что она отображает $X$ в полный прообраз $X$ относительно $f$.

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

Справедливо следующее утверждение: число подмножеств конечного множества, состоящего из $n$ элементов, равно $2^{n}$. Результат доказывается методом математической индукции. База индукции: у пустого множества $\varnothing$ ($n=0$) только одно подмножество — оно само, и $2^{0}=1$. Шаг индукции: пусть утверждение установлено для множеств мощности $n$. Рассмотрим произвольное множество $M$ с кардинальным числом $n+1$. Если зафиксировать некоторый элемент $a_{0}\in M$, подмножества множества $M$ разделяются на два семейства:

1. $M_{1}$, элементы которого содержат $a_{0}$,
2. $M_{2}$, элементы которого не содержат $a_{0}$, то есть являются подмножествами множества $M\setminus \{a_{0}\}$.

Подмножеств второго типа по предположению индукции $2^{n}$, однако подмножеств первого типа ровно столько же. С одной стороны, из каждого подмножества второго типа можно получить подмножество первого типа добавлением элемента $a_{0}$. С другой стороны, из каждого подмножества первого типа можно получить подмножество второго типа удалением элемента $a_{0}$. Следовательно,

$2^{M}=M_{1}\bigcup M_{2}$ и $M_{1}\bigcap M_{2}=\varnothing$.

По индукционному предположению $\left|M_{1}\right|=2^{n}$ и $\left|M_{2}\right|=2^{n}$, то есть:

$\left|2^{M}\right|=\left|M_{1}\right|+\left|M_{2}\right|=2^{n}+2^{n}=2^{n+1}=2^{\left|M\right|}$.

См. также

• Аксиома множества подмножеств
• Теорема Кантора
• Континуум-гипотеза

Литература

• Брудно А. Л. Теория функций действительного переменного. — М.: Наука, 1971. — 119 с.