Булеан

Пусть $A$ — множество. Множество всех подмножеств множества $A$ называется булеаном $A$ (также степенью множества (англ. power set), показательным множеством или множеством частей) и обозначается $\mathcal P(A)$. Также оно обозначается $2^A$, так как оно соответствует множеству отображений из $A$ в $2 = \{ 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$.

Доказательство проведем методом математической индукции.

База. Если $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-\left\{a_0\right\}$.

Подмножеств типа (2) по предположению индукции $2^n$. Но подмножеств типа (1) ровно столько же, так как подмножество типа (1) получается из некоторого и притом единственного подмножества типа (2) добавлением элемента $a_0$ и, следовательно, из каждого подмножества типа (2) получается этим способом одно и только одно подмножество типа (1).

Следовательно имеем $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|$.

См. также

• Аксиома булеана
• Теорема Кантора
• Континуум-гипотеза

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.