06. Теоремы о счетных множествах. Множества мощности континуум

Если рассмотреть любое конечное множество и любое его собственное (непустое и не совпадающее с ним самим) подмножество, то элементов в подмножестве меньше, чем в сам множестве, т. е. часть меньше целого.

Обладают ли бесконечные множества таким свойством? И может ли иметь смысл утверждение, что в одном бесконечном множестве "меньше" элементов, чем в другом, тоже бесконечном? Ведь про два бесконечных множества мы можем пока только сказать, эквивалентны они или нет. А существуют ли вообще неэквивалентные бесконечные множества?

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

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

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

"После некоторых размышлений директор обратился к администратору и сказал:

– Поселите его в № 1.

– Куда же я дену жильца этого номера? – удивлённо спросил администратор.

– А его переселите в № 2. Жильца же из № 2 отправьте в № 3, из № 3 – в № 4 и т. д."

Вообще, пусть постоялец, живущий в номере K, переедет в номер K+1, как это показано на следующем рисунке:

Тогда у каждого снова будет свой номер, а № 1 освободится.

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

Первоначально участники съезда занимали все номера гостиницы, следовательно, между множеством космозоологов и множеством N Было установлено взаимно однозначное соответствие: каждому космозоологу дали по номеру, на двери которого написано соответствующее ему натуральное число. Естественно считать, что делегатов было "столько же", сколько имеется натуральных чисел. Но приехал ещё один человек, его тоже поселили, и количество проживающих увеличилось на 1. Но их снова осталось "столько же", сколько и натуральных чисел: ведь все поместились в гостиницу!

Мы пришли к удивительному выводу: если к множеству, которое равномощно N, добавить ещё один элемент, получится множество, которое снова равномощно N. Но ведь совершенно ясно, что делегаты-космозоологи представляют собой часть того множества людей, которые разместились в гостинице после приезда нового гостя. Значит, в этом случае часть не "меньше" целого, а "равна" целому!

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

Новый постоялец не удивился, когда на другое утро ему предложили переселиться в № 1000000. Просто в гостиницу прибыли запоздавшие космозоологи из галактики ВСК-3472, и надо было разместить ещё 999999 жильцов.

Но потом произошла какая-то накладка, и в эту же самую гостиницу приехали на съезд филателисты. Их тоже было бесконечное множество – по одному представителю от каждой галактики. Как же их всех разместить?

Эта задача оказалась весьма сложной. Но и в этом случае нашёлся выход.

"В первую очередь администратор приказал переселить жильца из № 1 в № 2.

– А жильца из № 2 переселите в № 4, из № 3 – в № 6, вообще, из номера N – в номер 2n.

Теперь стал ясен его план: таким путём он освободил бесконечное множество нечётных номеров и мог расселять в них филателистов. В результате чётные номера оказались занятыми космозоологами, а нечётные – филателистами... Филателист, стоявший в очереди N-м, занимал номер 2n-1". И снова всех удалось разместить в гостинице. Итак, ещё более удивительный эффект: при объединении двух множеств, каждое из которых равномощно N, вновь получается множество, равномощное N, т. e. даже при "удвоении" множества мы получаем множество, эквивалентное исходному!

Определение. Множество А, равномощное множеству натуральных чисел N, называется Счетным множеством (имеет мощность счетного множества). Если множество В является бесконечным и не равномощно множеству N, то его называют несчетным.

Множество, которое является конечным или счетным, еще называют не более чем счетным.

Пусть множество А является счетным. По определению, тогда существует биекция А на N, т. е. каждому аÎА соответствует единственный номер nÎN и множество А обращается в некоторую последовательность {аn}.

Теорема 1. Любое подмножество счетного множества не более чем счетно.

Доказательство. Пусть А = {an} - счетное множество и В Í А. Если В конечное множество, то утверждение доказано. Предположим, что В бесконечное множество. Те элементы А, которые попали в В будут иметь некоторые номера в порядке возрастания: . Тогда необходимая нам биекция, показывающая, что В является счетным множеством, задается в виде: ® k.

Теорема 2. Объединение конечного или счетного числа счетных множеств является счетным множеством.

Доказательство. Рассмотрим счетное объединение счетных множеств (случай конечного является частным). Итак, пусть Аn - счетные множества для любого nÎN и А = Èn Аn. Для доказательства нам необходимо указать биекцию множества А на множество N, т. е. указать каждому аÎА его номер. Запишем все множества А в виде последовательностей с двумя индексами, где первый указывает номер множества. Зададим закон, который каждому элементу А ставит в соответствие некоторый порядковый номер. Если элементы множества Аn обозначить через аnk, то высотой элемента аnk назовем число n + k. Перепишем элементы множества А, располагая все его элементы по следующему правилу - сперва перепишем все элементы высоты 2, затем высоты 3, 4 и т. д: а11, а12, а21, а13, а22, а31, а14, а23, а32, а41, ... Тогда любой элемент множества А будет иметь определенный номер.

Теорема 3. Любое бесконечное множество содержит счетное подмножество.

Доказательство. Выберем в заданном множестве А какой-либо элемент, придав ему единичный индекс: а1. Среди всех оставшихся элементов множества А найдется не равный а1 элемент (в силу бесконечности А). Его мы обозначим через а2. Продолжая этот процесс до бесконечности мы получим необходимое нам счетное множество {an} .

Теорема 4. Пусть множество М - несчетно, множество А не более чем счетно и А Í М. Тогда множество М – А равномощно множеству М.

Доказательство. Пусть множество М – А не более чем счетно. Тогда множество М = АÈ(М – А) по теореме 2 не более чем счетно. Это противоречит тому, что множество М несчетно и, следовательно, наше исходное предположение не верно. Таким образом, множество М – А несчетно. Последнее еще не означает равномощности множеств М и М – А. Докажем ее. Выделим из М – А счетное множество В. Обозначим через С множество С = (М – А) – В. Справедливы равенства М = АÈВÈС и М – А = ВÈС. Множество АÈВ счетно (теорема 2). Следовательно, существует биекция f из АÈВ на А. Теперь можно построить биекцию g из М на М – А по правилу:

Теорема 5. Если множество С бесконечно, а В не более чем счетно, то множество ВÈС равномощно множеству С.

Доказательство. Если множество С счетно, то множество ВÈС также счетно и следовательно они равномощны. Если же множество С не счетно, то мы можем воспользоваться теоремой 4, положив в ней А = СÇВ, а М = С.

Теорема 6. Если множество С является бесконечным, то существует его подмножество В такое, что В¹С и В равномощно с С.

Доказательство. По теореме 3 мы можем выделить из множества С его счетное подмножество А. Если множество С счетно, то в качестве В из утверждения теоремы можно взять В=А. Если же С не счетно, то можно положить В=С-А и утверждаемое вытекает из теоремы 4.

Теорема 7. Множество рациональных чисел Q является счетным.

Доказательство. Обозначим через Р множество всех пар натуральных чисел (p, q), таких что p и q не имеют общих целых делителей, кроме единицы. Для пары натуральных чисел (p, q) введем ее высоту m = p + q. Обозначим Рn множество пар натуральных чисел высоты n. Нетрудно проверить, что каждое множество Рn является конечным и содержит не более, чем n-1 член. Так как Р = Èn Рn, то множество Р счетно в силу теоремы 2.

Рассмотрим теперь множество Q+ положительных рациональных чисел. Каждое положительное рациональное число представим в виде не сократимой дроби p/q. Тогда между этим числом и парами из Р существует биекция p/q « (p, q), которая показывает равномощность множеств Q +и Р, т. е. счетность множества Q+. Ясно, что множества Q+ и Q - равномощны. Тогда Q = Q +ÈQ - является счетным множеством как объединение двух счетных множеств.

Теорема 8. Множество точек интервала (0,1) является несчетным.

Доказательство (Диагональный метод Кантора). Доказательство проведем от противного, предположив, что множество точек интервала (0,1) является счетным. Тогда все точки можно записать в виде последовательности:

0,а11а12а12а14 ...

0,а21а22а23а24 ...

0,а31а32а33а34 ...

0,а41а42а43а44 ...

..........................

Покажем, что на самом деле здесь записаны не все числа из интервала (0,1). Построим число 0,а1а2а3а4 ... по правилу аk ¹ аkk. Это всегда можно сделать. Но тогда построенное нами число входит в интервал (0,1) и не совпадает ни с одним из записанных чисел. Мы получили противоречие с тем, что нами были выписаны все числа из интервала (0,1) и этим доказали теорему.

Множества, равномощные множеству точек интервала (0, 1), называются множествами мощности Континуум.

Задачи.

1. Показать, что если множества А и В являются счетными, то и их произведение А´В является счетным.

2. Установить биекцию между множеством N всех натуральных чисел и множеством Q всех четных положительных чисел.

3. Установить биекцию между множеством N всех натуральных чисел и множеством Р всех четных чисел.

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