Конечные и бесконечные множества
Понятия, введённые в §1 и §2, позволяют вывести из аксиом теории множеств основные свойства конечных и бесконечных множеств.
О п р е д е л е н и е. Говорят, что множество 
имеет 
элементов 
, и пишут 
, если существует последовательность с попарно различными членами и множеством значений (Она называется взаимно однозначной последовательностью с членами).
Множество называют конечным, если для некоторого 
; в противном случае оно называется бесконечным.
Множество имеет 0 элементов тогда и только тогда, когда 
, т.к. единственной последовательностью с 0 членами является пустая последовательность.
Для каждого 
множество 
имеет элементов. Действительно, функция Jp, заданная формулой Jp(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).
Дата добавления: 2018-04-04; просмотров: 417; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!