Равномощность множеств. Кардинальные числа.

Введем понятие равномощности множеств, одно из самых интересных и важных понятий теории множеств.

Определение. Два множества  и  равномощны, если существует взаимно однозначная функция  с областью определения  и множеством значений . В этом случае пишут  и говорят, что  устанавливает равномощность множеств  и .

Пример 1. Если - конечное множество, то множество  равномощно множеству тогда и только тогда, когда  имеет столько же элементов, что и . Таким образом, понятие равномощности обобщает на произвольные множества понятие равночисленности конечных множеств.

Пример 2. Пусть  - интервал ,

                          - интервал .

Функция  взаимно однозначна и отображает множество  на множество , т.е. .

Терема 1. Для произвольных множеств , , .

(I)

Д о к а з а т е л ь с т в о. Равномощность множества  самому себе устанавливает функция  (теорема 4 , §6, глава II).

Если функция  устанавливает равномощность множеств  и , то функция  устанавливает равномощность множеств  и  (теорема 1 , §6, глава II).

Если функция  устанавливает равномощность множеств  и , а функция - равномощность множеств  и , то суперпозиция  устанавливает равномощность множеств  и  (теорема 2 , §6, глава II).

Верны следующие формулы:

	(2)
,	(3)
	(4)
	(5)
	(6)
	(7)
	(8)
	(9)
	(10)

Мы опускаем доказательства (2-7), т.к. они не сложны (смотреть Е. Смупецкий, Л. Борковский «Элементы математики и теории множеств»). Докажем формулы (8-10).

Пусть , т.е. - функция двух переменных  и  (первая пробегает множество , вторая – множество ), значения которой принадлежат .

Для каждого фиксированного  функция (одной переменной ), определенная равенством , отображает  в , т.е. принадлежит множеству . Функция , определенная равенством , ставит в соответствие каждому  элемент множества , т.е. .

Если  и  - две различные функции, принадлежащие множеству , то соответсвующие им функции  и  также различны. В самом деле, если , то элементы  и  множества  различны.

Каждая функция  оказывается сопоставленной описанными выше способами некоторой функции , а именно функции , Определенной равенством , где .

Таким образом, сопоставляя функции  функцию , мы устанавливая взаимно однозначное отображение множества  на множество , т.е. формула (8) верна.

Чтобы доказать (9), заметим, что если , то  для каждого  является упорядоченной парой , где , .

Отсюда следует, что , .

Легко убедиться, что, сопоставляя функциям  пары , мы устанавливаем взаимно однозначное отображение множества  на множество .

Наконец, чтобы доказать (10), сопоставим каждой функции  уорядоченную пару сужений . Легко убедиться, что при этом множество  взаимно однозначно отображается на .

Формулы (2) и (8-10) представляют собой частные случаи следующих теорем.

Теорема 2 (закон коммутативности). Пусть . Если  - перестановка множества , то  (11)

Д о к а з а т е л ь с т в о.  Сопоставим каждой функции  суперпозицию . Если , то  для некоторого . Поэтому, полагая , получаем  или .

1) Таким образом, соответствие, установленное равенстом , взаимно однозначно.

2) Функция  принадлежит декартову произведению . В самом деле, если , то , т.е. .

3) Наконец, каждую функцию, принадлежащую декартову произведению , можно представить в виде , где . Для этого достаточно взять  равной .

Теорема 3 (закон ассоциативности). Пусть . Если  и все множества  попарно не пересекаются, то

 (12)

          (13)

Д о к а з а т е л ь с т в о.  Обозначим . Это множество таких функций  с областью определения , что , если . Множество  состоит, в свою очередь, из таких функций  с областью определения , что , если . Значение функции  будем обозначать . Это такая функция с областью определения , что .

Сопоставим функции  функцию , заданную равенством

   (*),

где - тот элемент множества , для которого .

Областью определения этой функции служит множество  и  для каждого . Следовательно, .

1) Отображение, сопоставляющее функциям  функции , взаимно однозначно. В самом деле, если , то существует такая , что , и поэтому существует такой элемент , что . Тогда в силу (*) .

2) Осталось показать, что каждая функция  сопоставлена некоторой функции . Для этого достаточно заметить, что функция , значение которой в точке  равно , принадлежит декартову произведению  и удовлетворяет равенству (*).

Для доказательства (13) достаточно в (12) положить  для каждого .

Теорема 4 (Закон возведения в степень декартова произведения). Пусть . Тогда для каждого множества

          (14).

Д о к а з а т е л ь с т в о.  Зададим на множестве  функцию  равенством .

Декартово произведение можно представить в виде суммы попарно непересекающихся множеств двумя различными способами :

,

где - множество всех пар со вторым элементом ,

- множество всех пар с первым элементом .

Например, .

,

Аналогично .

Дважды применяя теорему 3, получим

       (15)

       (16)

Для  имеем  и, значит, , откуда :

. Т.к. , то : , .

Из (15) получаем

         (17).

Сопоставляя при данном  функции  функцию , заданную равенством , убеждаемся, что , а в силу (16) :

           (18).

Формула (14) непосредственно следует из (17) и (18).

Если множества  и  равномощны, то говорят, что они имеют одинаковую мощность, или одно и то же кардинальное число. ( ) .

( - Кантор определял (???) мощность множества  как такое его свойство, которое остается после абстрагирования от:

a) качества ??? элементов множества ,

b) от их порядка.

- двойное отрицание подчеркивает этот двойной акт абстрагирования.

Разумеется ???, этим не оправдывается понятие мощности множества или его кардинального числа, а только вводится новый термин для понятия равномощности.

В конечном счете этот термин не обязателен, поскольку теоремы теории множеств можно сформулировать так, чтобы в них шла речь не о свойствах кардинального числа (или мощности), а об отношениях между ними, и эти отношения всегда можно доказать при помощи понятия равномощности.

Однако многие теоремы теории множеств становятся более обозримыми, если они сформулированы как теоремы о кардинальных числах. Это и оправдывает введение в теорию множеств кардинальных чисел.

Легко доказывается

Теорема 5. Для того, чтобы множество  и  были равномощны, необходимо и достаточно, чтобы реляционные ??? системы  и  были изоморфны.

Реляционный тип системы  будем обозначать символом  и называть кардинальным числом или мощностью множества .

Из теоремы 5 и аксиомы VIII (§ 10, глава II) вытекает

Теорема 6. Для произвольных множеств  и  условия  и  эквивалентны.

Эта теоремы позволяет представить результаты о равномощности множеств в виде равенств кардинальных чисел.

Счетные множества.

Пусть - конечное множество, содержащее  элементов, тогда теорема 6 § 1 выполняется, если положить .

В дальнейшем кардинальное число конечного множества будем отождествлять с числом его элементов.

Таким ообразом, теория мощностей конечных множеств не выводит нас за рамки арифметических натуральных чисел. Новые ситуации возникают только тогда, когда мы переходим к рассмотрению бесконечных множеств.

О п р е д е л е н и е. Множество  называется счетным, если оно конечно или равномощно множеству кардинальных чисел.

Очевидно, что любые два бесконечные счетные множества равномощны (смотреть теорему 1, § 1). Кардинальное число бесконечных счетных множеств обозначим через а ( - мощность радя натуральных множеств).

В главе III мы определили последовательность как функцию, областью определения которой служит множество натуральных чисел. Из этого определения следует, что бесконечное множество  счетно тогда и только тогда, когда оно служит множеством значений последовательности с попарно различными числами.

Допуская некоторую вольность, можно сказать, что множество  счетно, если его элементы можно «расположить» в бесконечную последовательность .

Теорема 1. Каждое непустое счетное множество является множеством значений некоторой бесконечной последовательности. И обратно, множество значений произвольной бесконечной последовательности счетно и непусто.

Д о к а з а т е л ь с т в о.  Конечное множество  есть множество значений бесконечной последовательности.

.

Бесконечное счетное множество есть по определению множество значений некоторой бесконечной последовательности.

Для доказательства обратного утверждения рассмотрим множество  значений бесконечной последовательности .

Пусть  и , где  или же , если нет такого , что .

По индукции легко доказать, что для каждого  существует такое , что . Отсюда следует, что  и, таким образом, все числа последовательности  различны. Осталось показать, что каждый элемент множества  будет числом последовательности .

Предположим, что множество  не является членом последовательности } непусто, и пусть - наименьший его элемент. Очевидно, что .

Если , то - член последовательности , например, . Пусть .

Наименьшее такое число , что , как раз и равно .

По определению последовательности  тогда , что противоречит выбору . Теорема доказана.

Аналогично доказывается