Множество всех подмножеств
Множество всех подмножеств (показательное множество, булеан множества — по имени Джорджа Буля (1815 - 1864), англ. математика и логика) — множество, состоящее из всех подмножеств данного множества <math>A</math> (включая пустое множество и само множество <math>A</math>); обозначается как <math>\mathcal P(A)</math>, или <math>\mathfrak B \left(A\right)</math>, или <math>2^A</math> (так как оно соответствует множеству отображений из <math>A</math> в <math>\{ 0,1\}</math>).
Если два множества равномощны, то равномощны и соответствующие множества всех подмножеств. Обратное утверждение (то есть инъективность операции <math>\kappa \mapsto 2^\kappa</math> для кардиналов) является независимым от ZFC.
В категории множеств можно снабдить функцию <math>\mathcal{P}</math> структурой ковариантного или контравариантного функтора следующим образом:
- ковариантный функтор отображает функцию <math>f\colon A\to B</math> в функцию <math>\mathcal{P}f\colon \mathcal{P}A \to \mathcal{P}B</math> такую, что она отображает <math>X</math> в образ <math>X</math> относительно <math>f\ </math>;
- контравариантный функтор отображает функцию <math>f\colon A\to B</math> в <math>\mathcal{P}f\colon \mathcal{P}B \to \mathcal{P}A</math> такую, что она отображает <math>X</math> в полный прообраз <math>X</math> относительно <math>f\ </math>.
Мощность конечного множества подмножеств
Справедливо следующее утверждение: число подмножеств конечного множества, состоящего из <math>n</math> элементов, равно <math>2^n</math>. Результат доказывается методом математической индукции. База индукции: у пустого множества <math>\varnothing</math> (<math>n=0</math>) только одно подмножество — оно само, и <math>2^0=1</math>. Шаг индукции: пусть утверждение установлено для множеств мощности <math>n</math>. Рассмотрим произвольное множество <math>M</math> с кардинальным числом <math>n+1</math>. Если зафиксировать некоторый элемент <math>a_0\in M</math>, подмножества множества <math>M</math> разделяются на два семейства:
- <math>M_1</math>, элементы которого содержат <math>a_0</math>,
- <math>M_2</math>, элементы которого не содержат <math>a_0</math>, то есть являются подмножествами множества <math>M \setminus \{ a_0 \}</math>.
Подмножеств второго типа по предположению индукции <math>2^n</math>, однако подмножеств первого типа ровно столько же. С одной стороны, из каждого подмножества второго типа можно получить подмножество первого типа добавлением элемента <math>a_0</math>. С другой стороны, из каждого подмножества первого типа можно получить подмножество второго типа удалением элемента <math>a_0</math>. Следовательно,
- <math>2^M = M_1 \bigcup M_2</math> и <math>M_1 \bigcap M_2 = \varnothing</math>.
По индукционному предположению <math>\left| M_1 \right| = 2^n </math> и <math>\left| M_2 \right| = 2^n </math>, то есть:
- <math>\left| 2^M \right| = \left| M_1 \right| + \left| M_2 \right| = 2^n + 2^n = 2^{n+1} = 2^\left| M \right|</math>.