Чарльз Петцольд - Читаем Тьюринга

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

Dauben, Georg Cantor, 285.

Глава 2. Иррациональные и трансцендентные числа 

45

Изучая бесконечные множества, Кантор сделал и другие удивительные открытия: он обнаружил, что можно установить взаимнооднозначное соответствие между континуумом – вещественными
числами на прямой – и точками двумерной плоскости и даже точками
любого N-мерного пространства.
Давайте ограничимся, например, участком плоскости с координатами x и y, заключенными между 0 и 1. Каждая точка на плоскости
может быть представлена парой чисел (x, y), и каждое из этих двух
чисел может иметь бесконечное число цифр после десятичной запятой. В следующем выражении каждая цифра числа x после десятичной запятой обозначается буквой a с индексом:
x = 0, a1 a2 a3 a4 ...
То же для y:
y = 0, b1 b2 b3 b4…
Теперь возьмем эти цепочки цифр и «сплетём» из них новое число:
0, a1 b1 a2 b2 a3 b3 a4 b4...
Получилось одно вещественное число, заключающее в себе два
вещественных числа. Каждая двумерная точка соответствует одному
вещественному числу континуума. Следовательно, множество точек
плоскости обладает той же мощностью, что и множество вещественных чисел прямой. Кантор был так поражен этим открытием, что изменил своему немецкому. «Je le vois, mais je ne le crois pa», – писал он
Дедекинду1. «Я вижу это, но я этому не верю».
В 1891 году Кантор опубликовал другое доказательство неперечислимости вещественных чисел2, и с тех пор оно так и осталось в умах
людей. Доказательство Кантора имело дело не с числами, а с множествами и было более общим, чем пример, который я собираюсь привести, но идея та же. По причинам, которые станут вполне понятными,
оно получило название диагонального доказательства, или диагонального процесса, или диагонального аргумента, или диагонализации.
Но как бы оно ни называлось, в его название входит слово диагональ.
Давайте ограничимся вещественными числами от 0 до 1. Предположим, что мы изобрели некий способ перечисления всех веществен1
2

Письмо от 29 июня 1877 года в From Kant to Hilbert, Vol. II, 860.
Georg Cantor, «On an Elementary Question in the Theory of Manifolds», From
Kant to Hilbert, Vol. II, 920–922.

46  Часть I. Основы
ных чисел. (Как можно догадаться, что это еще одно доказательство
от противного.) Допустим, список начинается как-то так:
0,1234567890…
0,2500000000…
0,3333333333…
0,3141592653…
0,0010110111…
0,4857290283…
0,0000000000…
0,9999999999…
0,7788778812…
0,2718281828…
...
Кажется, мы избежали хорошего начала. Список включает 0, 1/4,
1/3, /10, e/10, то странное иррациональное число с меняющимся
числом единиц, которое я приводил раньше, и некоторые другие, не
вполне узнаваемые числа. Каждое число в списке имеет бесконечное
количество десятичных разрядов (даже если они только нулевые), и
в нем – бесконечное количество чисел.
Хотя этот список бесконечен, мы можем убедиться, что в нем коечего нет. Посмотрим на цифры, образующие диагональ списка от левого верхнего угла к нижнему правому. Эти цифры выделены жирным шрифтом:
0,1234567890…
0,2500000000…
0,3333333333…
0,3141592653…
0,0010110111…
0,4857290283…
0,0000000000…
0,9999999999…
0,7788778812…
0,2718281828…
...
Теперь составим число из этих выделенных цифр:
0,1531190918…
Поскольку список вещественных чисел бесконечен и количество
цифр в каждом из них тоже бесконечно, у этого числа – бесконечное

Глава 2. Иррациональные и трансцендентные числа 

47

число цифр. Теперь увеличим каждую отдельную цифру этого числа
на 1 (цифра 9 меняется на 0):
0,26422010259…
Есть ли это новое число в исходном списке? Давайте действовать
последовательно: является ли это новое число первым в списке? Нет,
это не так, потому что первая цифра первого числа в списке – 1, а первая цифра нового числа – 2.
Является ли оно вторым числом в списке? И снова нет, потому что
вторая цифра второго числа в списке – 5, а вторая цифра нового числа – 6.
Является ли оно третьим числом в списке? Нет, потому что третья
цифра третьего числа в списке – 3, а третья цифра нового числа – 4.
И так далее. Новое число не может быть N-ым числом в списке, потому что N-ая цифра N-го числа в списке не равна N-ой цифре нового
числа.
Таким образом, список неполон, и наше исходное предположение
неверно. Невозможно перечислить вещественные числа от 0 до 1. Мы
еще раз убедились, что вещественные числа неперечислимы.
Что будет, если провести такой же эксперимент --">