Lex Kravetski (lex_kravetski) wrote,
Lex Kravetski
lex_kravetski

Category:

Бесконечная сортировка и ещё

Это вроде как дополнительные мысли, которые мне пришли уже после публикации предыдущей статьи, поэтому для понимания контекста этой и её нюансов в обязательном порядке следует целиком прочитать статью «Диагональный аргумент и бесконечные множества», поскольку содержание данной статьи плотно с ней связано и при этом не содержит тех разъяснений, которые уже есть в той, хотя на них ссылается.


Бесконечная сортировка



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

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

Теперь запомним какую-нибудь бесконечную (и пусть даже бесконечно повторяющуюся) последовательность цифр, соответствующую (или «равную», если считать допустимым приравнивание одного к другому) дробной десятичной части простой дроби.

Например,



Теперь сделаем вот что. Проверим, не стоит ли в первой ячейке число, первая цифра которого равна 1. Если стоит, то поменяем его местами с ближайшим следующим в таблице числом, у которого нет единицы в первой позиции.

После этого возьмём второе число и проверим, не стоит ли у него во второй позиции 4. Если стоит, то поменяем его с ближайшим следующим в таблице, у которого цифра во второй позиции другая.

Когда то же самое мы проделаем с семёркой в соответствующей позиции, снова перейдём к единице, которая следует за ней в бесконечном десятичном выражении числа, и так далее.

Заметьте, такую операцию всегда можно проделать — ведь на каждом шаге дальше в таблице всё ещё остаются числа, у которых на рассматриваемой нами позиции стоит какая-то другая цифра. Если бы это было не так, то оказалось бы, что в конечное количество предыдущих строк вписано бесконечное количество чисел: абсолютно все те, у которых на данной позиции цифра не такая.

При этом обмен чисел местами не меняет их количества, и, таким образом, не может изменить мощность множества.

Теперь, как принято, «погасим софиты» и представим, что мы дошли до конца бесконечной таблицы. Благодаря нашим манипуляциям ни в одной из её строк не должно быть 1/7 — ведь в каждой из них на диагонали стоит та цифра, которой нет в соответствующей позиции десятичного представления означенной дроби.

То есть минимум одно рациональное число осталось без номера.

То есть мощность множества рациональных чисел больше, чем натуральных.


То же самое, но без отвлечения внимания



Естественно, если убрать эти отвлекающие внимание манипуляции с цифрами, то логический просчёт окажется почти на поверхности.

Что на самом деле произошло? Пока мы не дошли до строки, в которой записана 1/7, мы просто меняли местами какие-то числа, и это ни на что не влияло.

Однако, когда до 1/7 мы всё-таки дошли, оно отъехало на какую-то из ближайших следующих строк. Потом мы снова до него дошли, и снова его переместили дальше по списку. Потом снова. И снова. И снова.

Пока мы находились в рамках непротиворечивого предположения «сколько бы строк мы уже ни прошли, всегда есть следующая», всё было в порядке — мы правда могли двигать это число всё дальше и дальше от начала. Причём для этого даже не надо было «подгонять цифры на диагонали» — просто можно было сказать «если мы нашли это число, то мы меняем его местами со следующим».

Но вот в тот момент, когда мы сказали «представим, что строки в таблице закончились», наступили последствия противоречия вида «окончание нескончаемого»: чудесным образом данное число «уехало» за пределы бесконечной таблицы.

Останься мы в рамках простой модели «просто поменяйте это число с соседним», такое было бы почти невозможно проглядеть. Из того, что, пока таблица не закончилась, всё ещё есть, куда двигать число, вовсе не следует, что его есть куда двигать, когда она чудесным образом закончилась.

Но введённое в систему предположений противоречие позволило нам в одном случае использовать некоторое утверждение: «всегда есть куда двигать», — а в другом случае взаимоисключающее с ним «мы перебрали все числа».

С конечной-то таблицей оно понятно: двигать можно не дальше, чем до последней строки, но с бесконечной уже как бы «всегда можно». Ну а потом, бабах, «бесконечное закончилось», однако двигать число почему-то по-прежнему было можно (что не озвучивалось напрямую, а просто предполагалось между строк), поэтому мы его как бы подвинули «за пределы бесконечного».

Тут может возникнуть вопрос: а точно ли это — то же самое, что и «диагональный аргумент»? Ведь тут мы что-то двигаем, а там «честно» строим «неуместное число» цифра за цифрой.

Ок, давайте ещё раз взглянем, как оно выглядело.

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

На самом деле, можно было не подбирать никаких цифр, а просто говорить: «для каждой строки мы берём то число, которое нам ещё не встречалось». Любым способом — безо всяких цифр на диагоналях.

Поскольку мы предполагаем, что чисел бесконечно много, то число, которое ещё не встречалось, всегда есть.

Точнее, не «всегда», а на каждом конечном шаге.

Но при этом мы позволили себе совершить бесконечный финальный шаг — тот, которого не могло быть по самому определению термина «бесконечный», что как раз и позволяло нам говорить про «всегда». И в этом мысленном эксперименте экстраполировали верное на каждом конечном шаге «всегда есть ещё не использованное число» на противоречивый «бесконечный шаг», почему-то продолжая считать оное верным и на нём тоже.

Фактически, мы позволили бесконечному количеству натуральных чисел закончиться в рамках нашего «мысленного эксперимента», но в нём же постулировали, что вещественные ещё не закончились («такое число всё ещё есть»), чем и доказали тезис «вещественных как бы больше».

Да, это было замаскировано какими-то манипуляциями с цифрами на диагонали, однако за всем этим скрывалось постулирование того, что мы собираемся доказать, и это после некоторой перефразировки вылилось в якобы доказанный тезис, по смыслу идентичный неявно постулированному.

Тут можно ещё заметить, что таким образом введённое понятие «актуальная бесконечность» подразумевает, что мы можем так пересортировать список, что одно число окажется «лишним», не меняя размера этого списка. И мы можем даже указать это число — бесконечную рациональную или иррациональную дробь. Или даже конечную — её-то мы тоже можем сколько угодно раз менять местами со следующей строкой, а потом «погасить софиты» и сказать «бесконечный список кончился, но подвинуть всё ещё было можно». Причём так мы можем сделать сколько угодно раз — исключая одно число за другим.

Или, как в оригинале доказательства, мы можем сказать «мы каждый подбираем число, которого ещё не было, потому что можем это сделать, но бесконечный список вдруг кончился, а такое число мы всё ещё можем назвать, потому что до этого шага такое всегда срабатывало».

В этом, собственно, и заключено принципиальная аналогичность этих двух «доказательств»: верное для каждого конечного шага ошибочно экстраполируется на противоречивый «гипотетический финальный шаг».


«Диагональный аргумент» для рациональных чисел напрямую



Если означенная экстраполяция считается допустимой, то с рациональными числами нам даже не обязательно прибегать к пересортировке. Давайте просто на каждом шаге ровно так же будем считать, что мы указываем на рациональное число, которое ещё не встречалось в списке рациональных же. На каждом шаге это возможно, гасим софиты, делаем экстраполяцию: на бесконечном шаге это всё ещё возможно, а натуральные числа уже кончились.

Почему?

А почему бы и нет? — вот почему. С иррациональными же так разрешается.

Этому, кроме того, помогает тот факт, что бесконечное количество цифр в десятичном представлении бывает не только у иррациональных чисел, но и у рациональных. Причём таких рациональных чисел тоже бесконечно много.

«Диагональный аргумент» пользуется тем, что десятичное представление иррационального числа на некотором «бесконечном шаге» выписывания этих цифр в точности равно самому числу, а не является пределом приближений к нему, поэтому про рациональные с бесконечным количеством знаков после запятой можно говорить точно так же.

Возьмём таблицу с нумерацией рациональных чисел и начнём строить число с бесконечной десятичной частью, но теперь уже не выбором произвольных цифр, а с выбором ровно тех, которые нужны для того, чтобы получающаяся дробь осталась рациональной даже с бесконечным количеством цифр. Причём нам нужно не какое-то конкретное число, а вообще любое рациональное с бесконечным количеством цифр.

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

Неизвестно — никто ведь не доказал, что можно, и никто не доказал, что нельзя.

Навскидку такая возможность выглядит крайне эфемерной (в частности, потому, что повторяющая часть у рационального числа может быть абсолютно любой длины и чисел с длиной, которая больше любой наперёд заданной, бесконечно много), а потому, видимо, невозможно: хоть какое-то рациональное число да подойдёт, какую бы нумерацию мы ни выбрали.

Но предположим, что всё-таки возможно. Мы как-то так всё хитро занумеровали, что ни одну из бесконечного количества рациональных дробей с бесконечной дробной частью так построить нельзя.

Хорошо. В этом случае внесём поправку в алгоритм: выбирая цифру для каждой из позиций, мы иногда позволим себе оставлять ту же цифру, которая была на этой позиции в этой строке — если то число, которое мы строим, не вписано в эту строку.

Нам ведь не обязательно, чтобы именно цифра не подходила для этой строки — нам надо, чтобы данное число ни разу не встретилось.

Чтобы это не сработало, нужна ещё более хитровывернутая нумерация: не просто всё бесконечное количество бесконечных рациональных дробей должно быть исключено очень хитрой расстановкой цифр на диагонали, но оно ещё и должно быть исключено так, чтобы при этом сохранение цифр там, где это возможно (а это возможно почти везде — кроме тех строк, в которые вписано само выстраиваемое нами число), не помогало.

Доказать возможность такой нумерации будет ещё сложнее — если, конечно, не делать доказательство самозамкнутым: «мощности множеств рациональных и натуральных чисел равны, а потому она возможна».

Если и этого будет мало, то обломившись на главной диагонали, мы сможем пройтись по диагонали, начинающейся с первой ячейки второй строки, предварительно убедившись напрямую в том, что то число, которое мы строим, не записано в первой строке. А если и этого не хватит, то с первой ячейки третьей строки — убедившись напрямую про первые две. И так далее.

А потом, после бесконечного количества попыток с бесконечным количеством чисел, ещё останутся диагонали, начинающиеся со второй ячейки первой строки, третьей ячейки первой строки и так далее.

А потом ещё можно сделать «диагональ не под сорок пять градусов»: первая ячейка в первой строке, третья — во второй, и так далее.

Реально ли вообще доказать, что возможна нумерация, исключающая все эти варианты одновременно для абсолютно всех рациональных чисел с десятичной дробной частью бесконечной длины?

Всю малину могло бы несколько испортить следующее соображение: если некое число, которое мы строим, вписано в таблицу в какой угодно строке, то у него совершенно точно цифра на соответствующей строке позиции совпадает сама с собой. И так у него с каждой цифрой на каждой позиции. И число само с собой тоже совпадает, поэтому оставить цифру мы не можем — надо менять. Если же в таблицу вписаны все бесконечные рациональные дроби, то такое будет иметь место для любого подходящего нам кандидата на «неуместное число». Что как бы говорит о том, что построить «неуместное число» невозможно.

Увы, для этого надо предположить, что все числа уже вписаны в таблицу. Но это предположение бы означало, что мощности множеств уже гарантированно совпадают, а значит ничего и не надо доказывать — мы это сразу постулировали в предположении. Доказательство стало бы самозамкнутым.

Если так можно, то ровно так же можно предположить, что и все иррациональные числа тоже уже вписаны в таблицу, а потому мы не можем построить не попадающее в таблицу иррациональное число — поскольку это противоречит предположению, что все они уже вписаны.

Если же не пользоваться самозамкнутыми доказательствами и этого не предполагать, то до того, как мы проверим всю таблицу, нет никакой гарантии, что некоторое число в неё уже вписано, поэтому и в случае с рациональными числами можно точно так же считать, что часть строк, подходящих для расположения в них некоторого числа, мы отмели прямой проверкой того, что там стоит не это число, а всю остальную часть — подбором цифры в соответствующей позиции, не соответствующей выстраиваемому числу. При этом последовательность всех этих цифр сложится в некоторое рациональное число (напомню, мы специально так выбираем альтернативные цифры, чтобы оно сложилось), которое как раз и будет «неуместным».

Интуиция, правда, подсказывает нам, что должно остаться, но она и про иррациональные подсказывает то же самое, однако там мы ей почему-то не поверили, поскольку у нас ведь есть «математическое доказательство». Тоже основанное на скрытом противоречии, однако противоречие в обоих случаях одно и то же, а потому либо в обоих случаях должно быть допустимым, либо в обоих нет. Я при этом, конечно, за второй вариант, но почему бы и нет — желающие могут выбрать первый. И считать, что таким образом доказано, что мощность множества рациональных чисел больше, чем у множества натуральных, хотя ранее было доказано, что они равны.

Разумеется, все эти ещё более сложные, чем у Кантора, построения, как и раньше сводятся к «мы просто каждый раз будем выбирать то число, которое ещё не встречалось, поскольку это всегда возможно, а потом погасим софиты», однако манипуляции с цифрами как бы «придают им убедительности». Тот момент, который происходит на большинстве шагов, выглядит «железно непротиворечивым», а актуальную бесконечность представить себе очень тяжело, поэтому произвольный вроде бы такой малюсенький переход к ней мозг себе как бы прощает под соусом «ну, я-то, быть может, не совсем точно себе это представляю, но тут всё, вроде как, логично выглядит».

Однако и в рассмотренных тут «доказательствах» именно в этом «одном малюсеньком переходе» сокрыт главный подвох: он противоречив.



doc-файл

Tags: наука
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 10 comments