Пример 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, которая принадлежала