В феврале 2020 года в интернет-издании «XX2 век» вышла статья известного блогера и популяризатора математики, логики и программирования Лекса Кравецкого под названием «Диагональный аргумент и бесконечные множества». В этой статье автор приводит интересные рассуждения о природе бесконечности в математике и подвергает критике так называемый диагональный аргумент (впервые предложенный математиком Георгом Кантором в конце XIX века) и правомочность использования данного приёма в доказательствах математических утверждений. Статья вызвала бурную реакцию в научно-просветительском сообществе, и в нынешнем виде предваряется замечанием редактора издания «XX2 век», в котором приводится ссылка на специально написанный математиком Данияром Шамкановым комментарий под названием «Тонкости бесконечностей. Ответ математика на статью Лекса Кравецкого „Диагональный аргумент и бесконечные множества“». В этом комментарии Данияр Шамканов верно отметил, что в современной математике используется система аксиом Цермело—Френкеля с аксиомой выбора и на сегодняшний день нет оснований полагать, что в ней имеются какие-либо логические противоречия, которые были характерны для «наивной» теории множеств времен Георга Кантора и на которые пытался указывать Лекс Кравецкий. В этом же комментарии даются другие интересные замечания по данному вопросу с точки зрения современной математики. Однако, на взгляд автора данной статьи, в комментарии Данияра Шамканова недостаточно подробно рассмотрен, собственно, сам главный контраргумент Лекса Кравецкого, выдвинутый им против метода Кантора. В данной статье читателю предлагается проследить логику Кравецкого и сделать выводы о правомочности использования диагонального аргумента при доказательствах того или иного утверждения.
Итак, в своей статье Лекс Кравецкий, рассуждая о понятиях бесконечного множества и мощности множества, утверждает следующее: если диагональный аргумент работает для доказательства неравномощности натуральных и действительных чисел, то он работает и для самих натуральных чисел. А раз с помощью диагонального метода, утверждает далее Лекс Кравецкий, можно доказать неравномощность множества натуральных чисел самому себе, то мы приходим к очевидному противоречию, и сам метод доказательства, а именно диагональный метод Кантора (он же диагональный аргумент) не может быть использован в качестве серьёзного инструментария математика. И тут как по мановению волшебной палочки рушится не только основополагающее основание математического анализа — несчётность множества действительных чисел, — но также и доказательство невозможности универсального алгоритмического определения того, остановится ли некоторая машина Тьюринга, некоторые варианты доказательства теоремы Гёделя и бог весть что ещё! Однако давайте разберём самый главный контраргумент Кравецкого: неравномощность множества натуральных чисел самому себе.
Начнём с того, что Кравецкий верно вводит многие определения и приводит верные доказательства некоторых общеизвестных рассуждений. Так, он совершенно точно воспроизводит доказательство равномощности натурального ряда и множества всех дробных (рациональных) чисел. Также он схематично, но достаточно строго воспроизводит доказательство неравномощности натуральных и действительных чисел по Кантору. Схема проста: предположим, что натуральные и действительные числа равномощны. Тогда можно построить взаимно однозначное соответствие между всеми натуральными и действительными числами, иными словами можно пересчитать без повторений одни числа с помощью других. Представив действительные числа (в отрезке от 0 до 1, о чём Кравецкий не упомянул в своей статье, но мы вернёмся к этому позже) в виде десятичной дроби с 0 в целой части и произвольной бесконечной комбинацией цифр после запятой, мы можем построить гипотетическую таблицу всех таких «хвостов» десятичных дробей. Это и означает, что мы пронумеровали все такие числа. Однако, применяя диагональный аргумент, а именно меняя каждое значение на диагонали такой таблицы на любое другое, выпишем новую дробь, хвост которой будет содержать эти новые значения на диагонали в той же последовательности. Получим, что эта десятичная дробь не может стоять ни в одной строке таблицы, то есть мы получим противоречие с тем, что мы в самом деле перечислили все действительные числа на отрезке [0;1] в таблице. А значит исходное предположение, что мы можем выписать такую таблицу (то есть пронумеровать действительные числа натуральными), неверно, и множество натуральных чисел неравномощно множеству действительных (последнее мощнее). Те, кто желают изучить это доказательство, вполне могут прочитать эту часть статьи Лекса Кравецкого и прояснить для себя этот вопрос, однако автор рекомендовал бы обратиться к популярной книге известного математика Роджера Пенроуза «Новый ум короля». Иными словами, здесь нет чудес.
Чудеса начинаются в разделе статьи Кравецкого под названием «Мощность множества натуральных чисел не равна самой себе». Для доказательства утверждения, приведённого в названии этого раздела, Лекс Кравецкий предлагает следующее:
«Для натуральных чисел приписывание нуля в конце работает уже не так хорошо, как для множества действительных, поскольку позиционная запись чисел подразумевает, что приписывание нуля справа от натурального числа увеличивает его в десять раз. По этой причине вместо нуля будем использовать «пустое место», которое никак не меняет число. Чтобы же на него сослаться, в тексте будет использоваться знак «_» (подчёркивание)».
Далее Кравецкий приводит главное рассуждение:
«Предположим, что мы нашли способ сопоставления натуральных чисел натуральным.
Есть, например, очевидный: каждое натуральное число сопоставляется самому же себе. Однако чтобы суть диагонального метода легче отслеживалась, предположим, что есть и другие, и каким-то из них мы воспользовались.
Тогда мы имеем бесконечный список примерно такого вида.
1. 123
2. 57434
3. 915543
4. 7
5. …Как и раньше, разобьём каждое число на цифры и запишем всё это в таблицу.
…
Теперь снова пойдём по диагонали, меняя цифру или знак подчёркивания в каждой ячейке на какую-то другую цифру (на знак подчёркивания менять ничего не будем).
У нас получилось натуральное число, например «3232…». Оно не может стоять в первой строке, поскольку его первая цифра должна была бы быть «1», а она «3», не может стоять во второй, поскольку вторая цифра должна была бы быть «7», а она — «2» и так далее. Даже в четвёртой строке оно не может стоять, поскольку в четвёртой позиции у него не знак подчёркивания (оно должно было бы кончиться уже после первой цифры, но нет, не кончилось).
То есть в этой таблице просто нет места для такого числа.
Какой бы способ сопоставления натуральных чисел с натуральными же мы бы ни выбрали, будет число, не попавшее в нумерацию!»
Таким образом, Кравецкий «доказал», что множество натуральных чисел неравномощно самому себе (на первый взгляд аналогично тому, как мы выше это сделали для множеств натуральных и действительных чисел). Более того, Кравецкий предлагает и второе доказательство, для тех, кого смущает использование нижнего подчеркивания. Для этого он вводит альтернативный способ записи натуральных чисел:
«…можно воспользоваться ещё одним способом построения не имеющего номера числа: строить натуральное число не «спереди», а «сзади».
Пусть в таблицу цифры каждого из чисел вписываются в обратном порядке — в этом случае уже сгенерированные цифры в дальнейшем будут оставаться на своём месте.
Это, вдобавок, позволяет отказаться от знака «_», который тоже мог вызывать подозрения, и использовать в качестве заполнителя всё тот же «0» — ведь приписывание спереди целой части числа любого количества нулей точно так же не меняет число, как приписывание любого количества нулей сзади дробной части».
Очевидно, что и для данного построения натуральных чисел Кравецкий провёл те же рассуждения, применив диагональный аргумент и заключив, что такой способ построения натуральных чисел приводит к неравномощности их множества самому себе. Но верно ли это?
С построением натуральных чисел фокуса нет. Мы действительно вправе выписать такую таблицу чисел. Воспользуемся последним способом, который предлагает Лекс Кравецкий: будем добавлять нули к натуральным числам слева, которые означают, что нет вкладов в данное число от степеней 10 в десятичной системе счисления, или, аналогично, от степеней 2 в двоичной системе счисления, выше некоторой степени n−1 — позиции самой последней ненулевой цифры, отсчитанной справа. Мы будем для простоты записывать числа в двоичной системе счисления, что никак не умаляет общности наших рассуждений. Рассмотрим таблицу таких натуральных чисел, но, в отличие от способа записи их Кравецким, не будем выписывать эти числа в случайном порядке, а расположим их для начала в порядке возрастания сверху вниз:
…000
…001
…010
Поскольку мы расположили все числа по возрастанию, начиная с нуля, то на диагонали (и выше) стояли только нули, а значащие цифры заполняли лишь нижнюю треугольную часть таблицы (по построению). Таким образом, применяя диагональный «трюк» Кантора—Кравецкого (выписывая то, что стоит на диагонали второй таблицы), мы получили из вполне определённого натурального числа …000 другую конструкцию — ***111, в которой стоит бесконечное число единиц. Эту конструкцию Лекс Кравецкий, ловко оперируя термином «актуальная бесконечность», почему-то тоже неявно отнёс к натуральным числам. Однако это не так.
Заметим, что, располагая натуральные числа в произвольном порядке, как это предлагает Кравецкий, и проделывая тот же диагональный трюк, мы будем получать бесконечное количество вариантов таких странных «натуральных чисел», у которых, например, «вначале» стоит бесконечная последовательность единиц, которую мы обозначили ***, а затем идёт какая-то сколь угодно большая комбинация нулей и единиц, зависящая от выбора расположения натуральных чисел в такой таблице. На самом деле, Кравецкий доказал неравномощность натуральных чисел и некоторого множества, включающего в себя как все натуральные числа, так и как минимум бесчисленное множество комбинаций вида ***11101010101 и т.д, но также и других бесконечных слева последовательностей нулей и единиц. И нигде явно этого не сказал.
О чём-то таком сам Лекс Кравецкий, правда, догадывался, рассуждая в разделе «В чём тут фокус» следующим образом:
Естественно, такое «доказательство» работает только потому, что мы включили в рассмотрение числа, имеющие бесконечное количество цифр в своей десятичной записи. В том смысле, что «такие числа уже есть и уже лежат в таком-то множестве».
Последняя фраза, по Кравецкому, как раз и означает, что он хочет оперировать «актуальной бесконечностью» множества, включая в него как бы все возможные комбинации цифр даже формально означающие, что значение числа бесконечно большое. Действительно, если так сделать, то такое множество не будет равномощно множеству натуральных чисел, и фокус тут не в диагональном методе Кантора, а в том, чтобы по какой-то причине отождествить эти два множества.
Сам Кравецкий, по-видимому, не заметил, как совершил обычную логическую ошибку подмены одного понятия другим в процессе рассуждения. Он отождествил множество натуральных чисел и объединение множества натуральных чисел с ещё одним множеством с бесконечным числом элементов, представляющим любые бесконечные комбинации 0 и 1, нигде не заканчивающиеся слева бесконечной цепочкой нулей, в том числе, включающим в себя «числа» «начинающиеся» с бесконечного ряда единиц.
Забавно, что если бы дело ограничилось добавлением только «чисел», «начинающихся» с ***, то это не привело бы к неравномощности множеству натуральных чисел, ведь замена 0 на 1 и 1 на 0 дала бы взаимно однозначное соответствие такого множества с истинным множеством натуральных чисел, всегда начинающихся с …, и можно показать, что объединение двух счётных множеств счётно. Но Кравецкий настаивает, что необходимо рассматривать все возможные числа с бесконечным числом единиц слева (но необязательно заканчивающиеся слева ***), поскольку, по его определению актуально бесконечного множества, «они уже там есть». И в таком случае, действительно, это множество не будет равномощно натуральному ряду — доказательство за авторством Лекса Кравецкого смотри выше, оно абсолютно верное. Но вместо этого Кравецкий почему-то предпочитает ругать диагональный метод.
И всё же, по какой причине никто не рассматривает такие «бесконечные натуральные числа»? Ведь в то же время для действительных чисел всё обстоит именно так: там рассматриваются бесконечные комбинации 0 и 1 после запятой (в двоичном представлении эти комбинации просто означают вклады двойки в той или иной отрицательной степени, да они убывают, но их бесконечно много). Более того, диагональный аргумент, если обобщить, как раз показывает неисчислимость именно всевозможных бесконечных последовательностей нулей и единиц натуральными числами. Так почему же для действительных чисел это всё важно, а натуральные числа не обобщают так, как предлагает Кравецкий?
Всё дело в неразличимости бесконечно больших чисел. Все числа, которые строит Кравецкий и которые не начинаются с … (то есть с бесконечного ряда нулей слева), на самом деле неразличимы и обозначаются одним знаком бесконечности ∞. Этому значку придаётся строгий смысл: им обозначается предел строго возрастающей, но нигде не ограниченной сверху последовательности натуральных чисел. И именно в таком и только таком смысле им можно и нужно оперировать. Иными словами, в известной нам математике полагается, что ***11101010 = ***11111111 = ***10000100 = любая другая бесконечная слева комбинация 1 и 0, нигде не заканчивающаяся … = ∞. Здесь знак равенства стоит только в том смысле, что это один и тот же предел любой бесконечной возрастающей и не ограниченной сверху последовательности. Это, кстати, всё очень в духе того понятия о «потенциально бесконечном» множестве, которым так вдохновляется Лекс Кравецкий в конце своей статьи.
А что же с действительными числами? А их бесконечные хвосты вполне различимы, и это важно. Действительно, рассмотрим все десятичные дроби на отрезке [0;1]. Исключив тривиальные совпадения значений типа 0,100… и 0,011*** (в двоичной системе счисления просто приравняв их по определению, в десятичной системе это эквивалентно записи 0,500(0)=0,499(9), где скобки означают бесконечное повторение числа в скобках справа), для всех остальных всевозможных бесконечных комбинаций 0 и 1 после запятой можно строго и однозначно указать их особое место на числовой прямой. Более того, можно если не строго вычислить расстояние между ними, то указать минимальное и максимальное расстояния, между которыми эти два числа находятся друг от друга, для любого интересующего нас наперёд заданного масштаба нашей линейки. И мы можем уточнять эти расстояния для любой интересующей нас точности измерения. С огромным количеством бесконечно больших «натуральных чисел», построенным Лексом Кравецким, такое не пройдёт: для них будет неоднозначно определено расстояние между ними (точнее для большинства из них оно будет одинаково бесконечным, «таким же» бесконечным, как и расстояние от них до любого обычного числа). Каждое действительное число отличается от другого в смысле расположения на числовой прямой, и это важно, потому что даёт возможность строго определить предел бесконечной, но ограниченной и сходящейся к пределу последовательности действительных чисел. И это даёт возможность непротиворечиво рассуждать о пределах любой сходящейся последовательности действительных чисел, как тоже о действительном числе, который расположен на той же числовой оси.
Хочется выразить надежду, что мой короткий комментарий помог до конца осознать читателям издания «XX2 век» все тонкости, связанные с доказательством того или иного факта через так называемый диагональный аргумент. Выводы я предоставлю делать самим, но, на взгляд автора этой статьи, контраргумент Лекса Кравецкого не контраргумент.
