6 Найти булеан заданного множества. Проверить его мощность.
Если мощность конечного множества А равна , то число всех подмножеств А равно , то есть .
Множество всех подмножеств множества М называется булеаном и обозначается . Для конечных множеств выполняется: .
Определение. Множества А и В называются равномощными, если между их элементами можно установить взаимнооднозначное соответствие.
Заметим, что для конечных множеств это утверждение легко доказать. Для бесконечных множеств оно определят само понятие равномощности.
Определение. Множество А называется счётным, если оно равномощно множеству натуральных чисел : .
Очень упрощённо можно сказать, что данное бесконечное множество является счётным, если для его элементов можно установить нумерацию с помощью натуральных чисел.
Без доказательства примем ряд важных фактов:
1. Любое бесконечное подмножество множества натуральных чисел является счётным.
2. Множество является счётным.
3. Множество рациональных чисел является счётным (является следствием из предыдущего утверждения).
4. Объединение конечного числа счётных множеств является счётным.
5. Объединение счётного числа конечных множеств является счётным.
6. Объединение счётного числа счётных множеств является счётным.
Все эти утверждения, как можно видеть, позволяют достаточно успешно устанавливать факт, что данное множество является счётным. Однако сейчас будет показано, что не всякое бесконечное множества является счётным; существует множества большей мощности.
Правило умножения, использованное нами для вывода нескольких формул, является самым простым, но не всегда применимым способом. Рассмотрим задачу, требующую более сложного метода решения.
Определим
мощность булеана
.
Булеаном называется множество
всех подмножеств некоторого заданного
множества А.
Если A
=
{ a1,
a2,
...an
} , то булеан определится так:
= { , { a1 } , { a2 } , ...{ an } , { a1, a2 } , { a1, a3 } , ...{ a1, an } , ...
{ an - 1, an } , ......... { an-2, an-1, an } , ...{ a1, a2, ...an } } .
7 Найти все k-элементные подмножества данного множества и проверить их
количество.
Как подсчитать число k-элементных подмножеств в Nn для произволь- ного натурального числа k? Во-первых, очевидно, что при k > n это число равно 0. Если же k ≤ n, то будем строить все k-элементные подмноже- ства в Nn следующим образом. Возьмем произвольную перестановку мно- жества Nn, и возьмем первые k элементов в этой перестановке (т.е. те эле- менты, в которые перешли 1, 2, . . . , k). Ясно, что таким образом мы получим все k-элементные подмножества, причем каждое из них будет встречаться одно и то же количество раз. Это количество раз равно k!(n−k)!, поскольку перестановки первых k элементов и оставшихся n − k элементов не меняют выбранное подмножество. Поэтому для подсчета числа k-элементных под- множеств в Nn нужно разделить общее число перестановок на k!(n − k)!. Полученное число называется числом сочетаний из n элементов по k и обозначается через
n n! k = k!(n−k)!.
Поскольку допол- нение k-элементного множества в множестве из n элементов состоит из n−k элементов, количество k-элементных подмножеств в n-элементном множе- стве равно количеству (n−k)-элементных подмножеств в нем, что прекрасно