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

Пусть A — множество. Множество всех подмножеств множества A называется булеаном A (также степенью множества, показательным множеством или множеством частей) и обозначается $\mathcal P(A)$ или 2^A. Ясно, что $\varnothing \in \mathcal P(A)$ и $A\in \mathcal P(A)$.

Справедливо следующее утверждение:

Число подмножеств конечного множества, состоящего из n элементов равно 2n.

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

База. Если n = 0, т. е. множество пусто, то у него только одно подмножество — оно само, и интересующее нас число равно 2⁰ = 1.

Индукционный шаг. Пусть утверждение справедливо для некоторого n и пусть M — множество с кардинальным числом n + 1. Зафиксировав некоторый элемент $a_0\in M$, разделим подмножества множества M на два типа:

1. содержащие a₀,
2. не содержащие a₀, то есть являющиеся подмножествами множества $M-\left\{a_0\right\}$.

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

Поэтому число всех подмножеств множества M равно 2ⁿ + 2ⁿ = 2^{n + 1}.

См. также

• Аксиома булеана