Позволительно дать и такое определение счётного множества:
множество называется счётным, если его можно пересчитать, т. е. назвать какой-то его элемент первым; какой-то элемент, отличный от первого, – вторым; какой-то, отличный от первых двух, – третьим и т. д., причём ни один элемент множества не должен быть пропущен при пересчёте.
Как только какое-либо бесконечное множество удалось расположить в последовательность отличных друг от друга элементов, так сразу возникает его взаимно однозначный пересчёт: член последовательности, стоящий на первом месте, и только он, объявляется первым; член, стоящий на втором месте, и только он, – вторым и т. д. Возьмём, к примеру, множество всех слов, составленных из букв a и b, и расположим его в последовательность:
A, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, …, baaba, baabb, ….
Правило расположения слов в последовательности мы выбрали таким (а могли бы выбрать и другим): группируем слова по длине, а в пределах группы располагаем их в алфавитном порядке. Раз множество всех слов в двухбуквенном алфавите удалось расположить в последовательность различающихся элементов, значит, оно счётно. Аналогичным образом можно расположить в последовательность различающихся элементов и множество слов в любом другом алфавите. Поэтому имеет место следующий фундаментальный факт: каков бы ни был алфавит, множество всех слов в этом алфавите счётно.
Пример 42. Доказать, что объединение счётного множества A с конечным множеством B является счётным множеством.
Пусть A = {a1, a2, a3, …, an, …} и B = {b1, b2, b3, …, bn}. Тогда их объединение A ∪ B можно расположить в последовательность {b1, b2, b3, …, bn, a1, a2, a3, … an, …}. Элемент a1 получит в этой последовательности номер (n + 1). Следовательно, объединение счётного и конечного множеств счётно.
Пример 43. Доказать, что объединение счётного множества A со счётным множеством B является счётным множеством.
Пусть A = {a1, a2, a3, …, an, …} и B = {b1, b2, b3, …, bn, …}. Тогда их объединение A ∪ B можно расположить в последовательность {a1, b1, a2, b2, a3, b3, …, an, bn, …}. Значит, объединение двух счётных множеств счётно.
Пример 44. Доказать, что всякое бесконечное множество M содержит счётное подмножество.
Так как множество M бесконечно, в нём имеется какой-то элемент, который мы обозначим a1. Бесконечное множество не может исчерпываться этим единственным элементом, поэтому в M присутствует ещё какой-то, отличный от a1 элемент, который мы обозначим a2. Но и этими двумя элементами не исчерпывается бесконечное множество, поэтому в нём найдётся элемент a3, отличающийся как от a1, так и от a2. Продолжая процесс, мы выделим из множества M счётное подмножество {a1, a2, a3, …}. Итак, всякое бесконечное множество содержит счётное подмножество.
Когда автор этих строк в 1947 г. пришёл студентом на мехмат Московского университета, он ещё застал замечательное выражение разве что счётное множество, означающее множество, являющееся конечным или счётным. Хотелось бы вдохнуть в него новую жизнь, и потому примеры 45 и 46 мы сформулируем с его использованием.
Пример 45. Доказать, что всякое подмножество разве что счётного множества разве что счётно.
Если объемлющее множество конечно, то всякое его подмножество конечно. Если же оно бесконечно, то расположим его элементы в последовательность β с неповторяющимися членами. Те члены этой последовательности, которые принадлежат интересующему нас подмножеству, естественным образом образуют конечную или бесконечную подпоследовательность последовательности β, что и доказывает, что это подмножество конечно или счётно. Итак, всякое подмножество разве что счётного множества разве что счётно.
Пример 46. Доказать, что объединение М ∪ С бесконечного множества M с разве что счётным множеством C содержит столько же элементов, сколько и M.
Напомним, что через C \ M обозначается множество всех тех элементов С, которые не являются элементами M. Заметим, что М ∪ С = М ∪ Н, где H = C \ M, причём H разве что счётно и не пересекается (т. е. не имеет общих элементов) с M. Если мы сумеем установить взаимно однозначное соответствие между M и М ∪ Н, то провозглашённый в примере 46 факт будет доказан.
Мы поступим так. Множество M разобьём на два непересекающихся множества A и B: M = A ∪ B, а множество М ∪ Н на два непересекающихся множества K и L: М ∪ Н = K ∪ L. Затем установим два взаимно однозначных соответствия: соответствие η между A и K и соответствие θ между B и L. При этом автоматически возникнет соответствие между множеством A ∪ B, равным M, и множеством K ∪ L, равным М ∪ Н, каковое соответствие, в силу того что A не пересекается с B, а K не пересекается с L, будет взаимно однозначным.
Приступаем к осуществлению плана. Выделяем в М счётное подмножество R. Полагаем A = M \ R, B = R, K = M \ R, L = R ∪ Н. В качестве η берём соответствие тождества, при котором каждый элемент соответствует сам себе. Множество R счётно, а множество H конечно или счётно. Поэтому (см. примеры 42 и 43) множество L счётно и между ним и B существует взаимно однозначное соответствие. Одно из таких соответствий берём в качестве θ. Итак, объединение бесконечного множества с разве что счётным множеством содержит столько же элементов, сколько и бесконечное множество.
В § 8 мы уже встретились с примером бесконечного множества, не являющегося счётным. Это было множество Ω всех бесконечных двоичных последовательностей. Множество называется несчётным, если оно бесконечно и не является счётным. Можно было бы сказать и так: множество называется несчётным, если оно не является разве что счётным. Сам факт существования несчётных множеств весьма принципиален, поскольку показывает, что бывают бесконечные множества, количество элементов в которых отлично от количества элементов натурального ряда. Установление данного факта в XIX в. Георгом Кантором является одним из крупнейших открытий в математике.
В этом параграфе будет показано, что некоторые из хорошо известных множеств несчётны. Среди таких множеств – прямая (понимаемая как множество её точек), луч, отрезок и интервал. Напомним, что интервал]a; b[состоит из всех точек, расположенных между точками a и b, тогда как отрезку [a; b], помимо указанных точек, принадлежат ещё и сами точки a и b.
Но прежде всего следует сказать об аксиоме вложенных отрезков. Список аксиом геометрии включает одну или несколько (в зависимости от выбранной версии списка) так называемых аксиом непрерывности, которые обеспечивают непрерывность прямой. Понятно, что данная фраза требует разъяснения. Дадим его в форме иллюстрации.
Допустим, мы должны воткнуть иглу циркуля в точку прямой, заданным раствором описать окружность и найти точку пересечения этой окружности с исходной прямой. Теперь вообразим, что такой точки мы не находим, потому что там, где мы рассчитываем её обнаружить, в прямой дырка. «Но это невозможно!» – с возмущением воскликнет читатель. Однако подобная невозможность как раз и обеспечивается аксиомами непрерывности. Представим себе, что прямая содержала бы только точки с рациональными координатами, а нужная нам точка имела бы координату √2 и потому отсутствовала бы на прямой. Аксиомы непрерывности и гарантируют присутствие на прямой точек с любыми действительными координатами и тем самым возможность отождествления точек прямой с действительными числами, координатами этих точек. Говорят, что точки прямой (или соответствующие им действительные числа) образуют континуум. Латинское прилагательное continuus (это в мужском роде, а в среднем – continuum) как раз и означает 'непрерывный, сплошной, связный, продолжающийся без перерыва, не имеющий ни скачков, ни пробелов'. Можно говорить о континууме точек на интервале или на отрезке, но говорить, скажем, о континууме рациональных точек нельзя.
Известны несколько вариантов аксиомы (или аксиом) непрерывности, из которых мы выберем такой:
Пусть дана бесконечная последовательность вложенных друг в друга отрезков:
[a1; b1] ⊃ [a2; b2] ⊃ [a3; b3] ⊃ … ⊃ [an; bn] ⊃ ….
Существует точка, принадлежащая всем этим отрезкам.
Это и есть аксиома о вложенных отрезках. (Подумайте, почему в формулировке аксиомы нельзя заменить отрезки интервалами.)
Пример 47. Доказать, что множество точек прямой несчётно.
Доказательство ведём от противного. Допустим, что это множество счётно и перенумеруем его: x1, x2, x3, …, xn, …. Образуем последовательность вложенных отрезков по следующему принципу: отрезок [ak; bk] не должен содержать ни одну из точек x1, x2, x3, …, xk. Тогда не найдётся ни одной точки xn, которая принадлежала бы всем отрезкам, что нарушает аксиому. Итак, множество точек прямой несчётно.
Совершенно так же доказывается несчётность отрезка, интервала, открытого (без вершины) и замкнутого (включая вершину) луча. Каждая из этих геометрических фигур понимается в данном случае как множество своих точек. Более того, все эти множества оказываются равномощными; говорят, что они континуальны или что они имеют мощность континуума. Сейчас мы докажем заявленную равномощность.
Пример 48. Доказать, что все отрезки на числовой прямой равномощны. Достаточно доказать равномощность произвольного отрезка [a; b] единичному отрезку [0; 1] (тогда все отрезки окажутся равномощными в силу принципа транзитивности). Формула y = (1 – t)a + tb, где t пробегает [0; 1], даёт требуемое взаимно однозначное соответствие между [0; 1] и [a; b]. Приводимая формула имеет наглядную физическую интерпретацию: точка y едет с постоянной скоростью от левого конца отрезка [a; b] к правому и достигает цели в течение единичного интервала времени; каждому моменту единичного интервала соответствует положение точки в этот момент. Следовательно, все отрезки на числовой прямой равномощны.
