Мощности множеств и комбинаторика
Мощность конечного множества
Как уже отмечалось, если А -- конечное множество, то его
мощность 
есть количество элементов,
принадлежащих А.
Легко видеть, что
1). Если 
, то 
=
+
2). В общей ситуации: 
3). 
Теорема 1. Если 
,…,
- конечные множества, то
=
Доказательство непосредственно следует из подсчета числа различных n-ок.
Следствие. Если А -- конечное множество, то 
Теорема 2. Два конечных множества равномощны тогда и только тогда, когда между ними существует биекция.
Доказательство очевидно.
Следствие. Никакое собственное подмножество или надмножество
конечного множества 
не равномощно множеству А.
Теорема 3. Пусть A- конечное множество, 
множество всех подмножеств
(булеан) множества А. Тогда | 
.
Доказательство. Рассмотрим 
и пусть 
. Тогда 
-- множество бинарных n-ок. Существует биекция между и
. Действительно, пусть 
и 
т. е. 
Поставим в соответствие множеству М
такую n-ку 
, в которой i-ый
элемент равен 1, если 
, и равен 0, если 
. Обратно, всякой бинарной n-ке однозначно соответствует
некоторое множество М, элементы которого определяются по n-ке описанным выше
способом. Поскольку биективные множества имеют равное количество элементов
(теорема 2) и 
n (следствие
к теореме 1), то 
n, что и требовалось доказать.