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

Множество всех подмножеств множества из 3 элементов

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

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

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

• ковариантный функтор отображает функцию $f:A\to B$ в функцию $𝒫f:𝒫A\to 𝒫B$ такую, что она отображает $X$ в образ $X$ относительно $f$;
• контравариантный функтор отображает функцию $f:A\to B$ в $𝒫f:𝒫B\to 𝒫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|}$.

См. также

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

Литература

• Шаблон:Книга