мощность всех подмножеств данного множества.

Введем обозначения:
ф - пустое множество
M(A) - множество всех подмножеств A

Пусть А = ф. Тогда |A| = 0. Единственным элементом M(A) является ф, следовательно, |M(A)| = 1

Пусть А состоит из одного элемента: А ={a}. Тогда |A| = 1. M(A) = {ф, A}, следовательно, |M(A)| = 2

Выдвигаем гипотезу: Если |A|=n, то |M(A)| = 2^n

Для случаев пустого и одноэлементного множеств гипотеза верна.

Предположим, что гипотеза верна для А такого, что |A|=n.

Добавим к А один элемент: A' = A U {b}.
Тогда |A'|=n+1

В то же время:
M(A') = M(A) U {G U {b} | G - элемент M(A)}
т. е. M(A') состоит из множеств, являющихся элементами M(A), а также их объединений с новым элементом b.

Получаем:
|M(A')| = |M(A)| +|{G U {b} | G - элемент M(A)}| =
|M(A)| +|M(A)| = 2 |M(A)| = 2 * 2^n = 2^(n+1)