Пусть M – произвольное множество. Его мощность обозначается |M|. Если множество M состоит из конечного числа элементов, то |M| – число его элементов. Обозначим через 2M = {A: A Í M} – множество всех подмножеств множества M.
Теорема
Если множество М имеет конечное число элементов, то | 2M | = 2| M |.
Доказательство
Таблица 1.1 Перебор подмножеств множества {a,b,c}
|
Номер |
Двоичная запись |
Подмножество |
|
0 |
000 |
Æ |
|
1 |
001 |
{c} |
|
2 |
010 |
{b} |
|
3 |
011 |
{b, c} |
|
4 |
100 |
{a} |
|
5 |
101 |
{a, c} |
|
6 |
110 |
{a, b} |
Пусть M = {a0, a1, ××××, an-1}. Каждому подмножеству можно поставить в соответствие битовую строку, состоящую из n разрядов, равных 0 или 1. Эта битовая строка представляет собой двоичную запись некоторого неотрицательного целого числа. Ее i-й разряд равен 1, если ai Î A, и равен 0, в других случаях. Хорошо известно, что количество двоичных n-разрядных чисел равно 2n. Следовательно, количество подмножеств будет равно 2|M|.
Упражнение
Докажите предыдущую теорему с помощью индукции по числу элементов множества M.
Замечание
Получаем алгоритм перебора подмножеств. Каждому подмножеству соответствует неотрицательное целое число, двоичная запись которого содержит единичные разряды, соответствующие элементам этого подмножества. Прибавляя по 1, получаем все подмножества. Например, для M = {a, b, c} этот алгоритм можно проиллюстрировать с помощью таблицы 1.1.