2. Счетность множества рациональных чисел и несчетность континуума

Одно из первых открытий Кантора в области анализа бесконечного заключалось в том, что множество рациональных чисел (содержащее в качестве правильного подмножества бесконечное множество натуральных чисел и потому само бесконечное) эквивалентно множеству натуральных чисел. На первый взгляд кажется странным, что всюду плотное множество рациональных чисел не более богато элементами, чем множество натуральных чисел, элементы которого "рассеяны" редко и стоят на значительном расстоянии один от другого. И в самом деле, с сохранением порядка возрастания нельзя расположить положительные рациональные числа так, как это можно сделать с натуральными: самое маленькое число а будет первым, следующее за ним по величине b вторым и т. д.; дело в том, что рациональные числа расположены всюду плотно, и потому ни для одного из них нельзя указать "следующего по величине". Но Кантор заметил, что если отказаться от требования "располагать по величине", то тогда оказывается возможным расставить все рациональные числа в ряд r₁, r₂, r₃, r₄,..., подобный ряду натуральных чисел. Такое расположение предметов некоторого множества в виде последовательности часто называют пересчетом ("нумерацией") этого множества. Множества, для которых пересчет может быть выполнен, называются счетными или исчислимыми. Указывая один из способов пересчета множества рациональных чисел и устанавливая, таким образом, его счетность, Кантор тем самым показал, что это множество эквивалентно множеству натуральных чисел, так как

схема создает взаимно однозначное соответствие между двумя множествами. Мы опишем сейчас один из возможных способов пересчета множества рациональных чисел.

Рис. 19. Пересчет рациональных чисел

Каждое рациональное число записывается в виде где а и b - целые числа; все эти числа могут быть расположены в виде такой таблицы, чтобы число стояло в а-й строчке и в b-м столбце. Например, станет в третьей строчке и в четвертом столбце таблицы. Предположим, что все свободные места, или "клеточки", в таблице заполнены соответствующими числами, а затем проведем по таблице непрерывную ломаную линию, которая пройдет через все клеточки. Начиная с 1, мы сделаем сначала один шаг вправо и получим 2 в качестве второго члена последовательности; затем по диагонали налево и вниз получим третий член следующий шаг прямо вниз даст нам четвертый член потом двинемся по диагонали вправо и вверх через к 3; вправо - к 4; по диагонали влево и вниз через и к и т. д., как показано на рис. 19. В результате движение по ломаной линии приводит к последовательности рациональных чисел

Если мы выбросим теперь все дроби, у которых числитель и знаменатель имеют отличные от 1 общие делители, то останется последовательность, в которой каждое рациональное число встретится в точности один раз:

Так устанавливается, что множество всех рациональных чисел является счетным. Принимая во внимание, что рациональные числа взаимно однозначно связаны с рациональными точками числовой прямой, можно также сказать, что множество рациональных точек на числовой прямой счетно.

Упражнения. 1) Покажите, что множество всех целых, положительных и отрицательных чисел счетно. Покажите, что множество всех рациональных, положительных и отрицательных чисел счетно.

2) Покажите, что если S и Т- счетные множества, то множество S + Т (см. стр. 138) также счетно. То же покажите для суммы трех, четырех и, вообще, n множеств; покажите, наконец, что множество, составленное посредством сложения счетного множества счетных множеств, также счетно.

Раз оказалось, что множество рациональных чисел - счетное, то могло бы возникнуть подозрение, что и всякое бесконечное множество также счетно и на этом, естественно, закончился бы весь анализ бесконечного. Но это совсем не так. Тому же Кантору принадлежит открытие исключительной важности: множество всех действительных (рациональных и иррациональных) чисел несчетно. Другими словами, совокупность всех действительных чисел - совершенно иного (так сказать, более высокого) "типа бесконечности", чем совокупность одних только целых или одних только рациональных чисел. Принадлежащее Кантору остроумное "косвенное" доказательство этого факта стало образцом для многих других доказательств в математике. Идея рассуждения такова. Мы исходим из допущения, что все действительные числа удалось перенумеровать, располагая их в виде последовательности, и после этого демонстрируем число, которое никак не может быть числом этой последовательности. Отсюда возникает противоречие: ведь было предположено, что все действительные числа вошли в состав последовательности, и это предположение должно быть признано ложным, если хотя бы одно число оказывается за пределами последовательности. Таким образом обнаруживается несостоятельность утверждения, что все действительные числа поддаются пересчету, и ничего другого не остается, как только признать вместе с Кантором, что множество действительных чисел несчетно.

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

где буквы N_i обозначают целую часть, а буквы а, b, с... представляют собой десятичные знаки, стоящие вправо от запятой. Мы допускаем, что эта последовательность дробей охватывает все действительные числа. Существенной частью доказательства является построение с помощью "диагональной процедуры" такого нового числа, относительно которого можно показать, что оно не входит в наш список.

Построим такое число. Для этого возьмем первую цифру после запятой а какую угодно, но отличную от ах, а также от 0 и 9 (последнее, чтобы избежать затруднений, возникающих из равенств вроде следующего: 0,999...= 1,000...); затем вторую цифру b возьмем отличной от b₂, а также от 0 и 9; третью цифру с - отличной от c₃ и т. д. (Для большей определенности можно условиться в следующем: мы берем а = 1, если только а₁ 1, а в случае а₁ = 1 возьмем а = 2; и аналогично для всех, прочих цифр b, с, d, е,...) Теперь рассмотрим число

Рис. 20. Взаимно однозначное соответствие между точками согнутого интервала и точками прямой линии

Это новое число z наверняка не входит в наш список; действительно, оно не равно первому числу, стоящему в списке, так как от него отличается первой цифрой после запятой, оно не равно второму числу, так как от него отличается второй цифрой после запятой, и вообще отлично от n-го числа по списку, так как отличается от него n-й цифрой после запятой. Итак, в нашем списке, составленном будто бы из всех действительных чисел, нет числа z. Значит, множество всех действительных чисел несчетно.

Читателю может прийти в голову мысль, что несчетность континуума обусловливается неограниченной протяженностью прямой линии и что конечный отрезок прямой будет содержать лишь счетное множество точек. Чтобы убедиться в ложности такого предположения, достаточно установить, что весь числовой континуум в целом эквивалентен некоторому конечному интервалу, скажем, единичному интервалу от 0 до 1. Получить необходимое для этой цели взаимно однозначное соответствие можно, например, сгибая интервал в точках и и затем проектируя так, как показано на рис. 20. Отсюда видно, что даже конечный интервал (и, конечно, отрезок) содержит несчетное множество точек.

Упражнение. Показать, что любой отрезок [А, В] числовой прямой эквивалентен любому другому отрезку [С, D] (рис. 21).

Рис. 21. Взаимно однозначное соответствие между точками двух отрезков различной длины

Стоит привести еще другое доказательство несчетности континуума, носящее, пожалуй, более интуитивный характер. Достаточно (принимая во внимание последнее доказанное предложение) сосредоточить внимание на точках единичного отрезка от 0 до 1. Доказательство, впрочем, как и раньше, будет "косвенное". Предположим, что множество всех точек названного отрезка может быть расположено в виде последовательности

Покроем точку ах интервалом, длина которого пусть будет равна точку а₂ - интервалом длины и т. д. Если бы все точки единичного отрезка входили в последовательность (1), то весь единичный отрезок оказался бы покрытым бесконечным множеством таких интервалов (может быть, частью перекрывающихся), длины которых суть (Беды нет, если некоторые из наложенных отрезков выйдут за пределы основного единичного отрезка.) Сумма всех длин наложенных отрезков равна

Итак, допущение, что последовательность (1) содержит всё действительные точки единичного отрезка, приводит к заключению, что весь этот отрезок, длина которого равна 1, можно покрыть множеством отрезков с общей длиной ; с интуитивной точки зрения это - нелепость. Это рассуждение мы позволим себе рассматривать как доказательство, хотя строго логически тут был бы нужен более глубокий анализ.

Приведенное только что рассуждение, между прочим, позволяет установить одну теорему, имеющую большое значение в современной "теории меры". Заменяя упомянутые выше промежутки меньшими промежутками - длины , где ε - произвольное малое положительное число, мы убедимся, что всякое счетное множество точек на прямой может быть покрыто множеством отрезков с общей длиной Так как ε произвольно мало, то и может быть сделано столь малым, сколь нам угодно. Пользуясь фразеологией "теории меры", мы скажем, что счетное множество точек имеет меру нуль. Упражнение. Доказать аналогичную теорему для счетного множества точек на плоскости, заменяя отрезки площадями квадратов.