1.3.1. Мощности множеств и комбинаторика. Мощность конечного множества

Как уже отмечалось, если А -- конечное множество, то его Мощность есть количество элементов, принадлежащих А.

Легко видеть, что

1). Если , То =+

2). В общей ситуации:

3).

Теорема 1. Если ,…,- конечные множества, то

=

Доказательство Непосредственно следует из подсчета числа различных n-ок.

Следствие. Если А -- конечное множество, то

Теорема 2. Два конечных множества равномощны тогда и только тогда, когда между ними существует биекция.

Доказательство очевидно.

Следствие. Никакое собственное подмножество или надмножество конечного множества не равномощно множеству А.

Теорема 3. Пусть A- конечное множество, W - множество всех подмножеств (булеан) множества А. Тогда | W = 2.

Доказательство. Рассмотрим и пусть . Тогда -- множество бинарных N-ок. Существует биекция между W и . Действительно, пусть и W, т. е. Поставим в соответствие множеству М такую N-ку , в которой I-ый элемент равен 1, если , и равен 0, если . Обратно, всякой бинарной N-ке однозначно соответствует некоторое множество М, элементы которого определяются по n-ке описанным выше способом. Поскольку биективные множества имеют равное количество элементов (теорема 2) и 2N (следствие к теореме 1), то W = 2N, что и требовалось доказать.

< Предыдущая		Следующая >