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

---

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

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

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

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

---