Перечисление подмножеств

Пусть 2^M = { A: A Í M } – множество всех подмножеств множества M.

Теорема 1. М – конечное Þ | 2^M | = 2^{| M |}

Доказательство. Пусть M = {a₀, a₁, ××××, a_n-1 } – множество. Каждому подмножеству соответствует битовая строка, состоящая из 0 и 1. Бит[i] = 1, если a_i ÎA, и Бит[i]=0, в других случаях. Хорошо известно, что количество двоичных n -разрядных чисел равно 2ⁿ .