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

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

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

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

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

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

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

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

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

Теория множеств

Potenční množina | Potenzmenge | Power set | Conjunto potencia | Potenssijoukko | קבוצת החזקה | Hatványhalmaz | Insieme delle parti | 冪集合 | Machtsverzameling | Potensmengde | Zbiór potęgowy | Conjunto de partes | 冪集