Конечные и бесконечные множества.

Понятия, введённые в §1 и §2, позволяют вывести из аксиом теории множеств основные свойства конечных и бесконечных множеств.

О п р е д е л е н и е. Говорят, что множество  имеет  элементов , и пишут , если существует последовательность с  попарно различными членами и множеством значений (Она называется взаимно однозначной последовательностью с  членами).

Множество  называют конечным, если  для некоторого ; в противном случае оно называется бесконечным.

Множество  имеет 0 элементов тогда и только тогда, когда , т.к. единственной последовательностью с 0 членами является пустая последовательность.

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

Теорема 1. Если функция  взаимно однозначно отображает множество  на , то условия  и  эквивалентны.

Д о к а з а т е л ь с т в о. Если - последовательность с  попарно различными членами и множеством значений , то  - последовательность с  попарно различными членами (см. теорему 2 §6, гл.II) и множеством значений .

Лемма. Если - взаимно однозначная функция, ,  и , то существует такая взаимно однозначная функция  с множеством значений , что .

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

Теорема 2. Пусть . Следующие условия эквивалентны:

I.

II. Существуют множества  и элемент , для которых  и .

III.  и, если для множества  и элементы , не принадлежащие ему, , то .

Д о к а з а т е л ь с т в о.

. Пусть - последовательность с  попарно различными членами и множеством значений . Взяв  и , получим условие II.

. Условие  непосредственно следует из II. Обозначим через  и  множество и элемент, удовлетворяющие условию II. Тогда  и, значит, существует взаимно однозначная функция, отображающая  на .

Согласно лемме, существует функция , взаимно однозначно отображающая  на ; следовательно,  в силу теоремы 1.

. Пусть - произвольный элемент множества  и . Согласно условию III,  и, значит,  - множество значений некоторой последовательности  с  попарно различными членами. Последовательность  с  членами, заданная равенствами  для , , имеет попарно различные члены, а множеством значений её является . Следовательно .

Теорема 3. Если , , то  тогда и только тогда, когда существует такое множество , что  является его взаимно однозначным образом.

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

Обратно, предположим, что существуют множество  и взаимно однозначная функция , отображающая  на .

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

Множество  или 1) пусть, или 2) равно .

В 1-м случае будет . Тогда поскольку , , можно применить индукцию и получить , а значит, .

Во 2-м случае в силу теоремы 2 , где . По предположению индукции , откуда , и теорема доказана.

Теорема 4. Если ,  и , то .

Д о к а з а т е л ь с т в о. Проведем индукцией по .

1) Для  и, значит, теорема верна.

2) Пусть теорема верна для некоторого числа , и пусть . Тогда , где , и потому , где . По предположению индукции тогда . Из Теоремы 2 следует, что . Т.к. по определению суммы , то теорема доказана.

Следствие 5. Семейство всех конечных подмножеств произвольного множества  образует идеал (см. (II) §5, гл.I).

Действительно, подмножество конечного множества конечно по теореме 3, а сумма конечных множеств конечна по теореме 3 и теореме 4.

Теорема 6. Если , , то множеств  является взаимно однозначным образом множества  и только тогда, когда .

Д о к а з а т е л ь с т в о. Если , то очевидно, что - взаимно однозначный образ множества , т.к. существуют последовательности с  попарно различными членами, отображающие множество  соответственно на  и .

Обратно, пусть - взаимно однозначный образ множества . Тогда - взаимно однозначный образ множества . Докажем по индукции, что .

1) Для  теорема верна (очевидно).

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

Следствие 7 (Принцип Дирихле). Если , , , то функция , для которой , не взаимно однозначна.

Сам Дирихле содержательно сформулировал этот принцип так:

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

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

Теорема 8. Если  бесконечно и , то и  бесконечно.

Это следует непосредственно из теоремы 3.

Теорема 9. Если  бесконечно, а  конечно, то разность  бесконечна.

Это следует из теоремы 4.

Теорема 10. Множество  бесконечно.

Д о к а з а т е л ь с т в о. Докажем методов от противного. Предположим, что , где . Т.к. , то в силу теоремы 3 множество  имеет  элементов, где  - такой элемент множества , что . Т.к.  для каждого , то , что приводит к противоречию выражению 4 (§1, гл.III).