Построение этого «числа» — ключевой момент доказательства, поскольку именно при помощи рассуждений об этом числе, вроде бы построенном на базе предположения о возможности занумеровать все вещественные числа, опровергается это самое предположение и делается вывод, что верно обратное — то есть занумеровать вещественные числа невозможно.
Само по себе сие содержит логический изъян, поскольку для полноты доказательства недостаточно продемонстрировать, что некоторое предположение приводит к противоречию — кроме того, надо ещё доказать, что к противоречию не приводит отрицание этого предположения. Что совершенно не обязательно.
И сейчас будет как раз тот самый случай, когда отрицание предположения тоже приводит к противоречию.
Предположим, что доказательство Кантора верно и, таким образом, вещественные числа невозможно занумеровать.
Любой конечный текст любого конечного алфавита может быть сохранён в виде последовательности битов, то есть, по сути, любой такой текст всегда является натуральным числом в любой выбранной нами системе кодирования.
Впрочем, это не менее очевидно, если учесть, что любой символ n-значного алфавита (который может включать пробелы, переводы строк и т.п.) может считаться уникальной «цифрой» в n-значной системе счисления, а любой конечный текст, таким образом, будет позиционной записью натурального числа в этой системе. Причём каждый конечный текст соответствует уникальному числу и наоборот.
«Определением» числа мы будем считать что угодно, что с нашей точки зрения позволяет нам его идентифицировать. Например, «определением» можно считать, в том числе, алгоритм построения некоторого числа, что имеет некоторые натяжки, но, так и быть, мы можем допустить и такое тоже.
По техническим причинам любое определение — конечно. Иначе мы просто не могли бы им пользоваться в рассуждениях. Отдельно подчеркну: всегда конечно именно определение, то есть сам текст. Но совершенно не обязательно конечно то, что он определяет.
Мы можем выкинуть все тексты, которые не определяют что-либо, а из каждого набора определяющих одну и ту же сущность оставить какой-то один. Поскольку любое определение — натуральное число, полученное множество определений всё равно можно будет пронумеровать натуральными числами, ведь такие тексты являются подмножеством натуральных чисел в нашей «алфавитной» позиционной записи.
Теперь в качестве того самого, фигурирующего у Кантора, «произвольного способа нумерации вещественных чисел» выберем сопоставление вещественного числа его определению, если таковое вообще есть.
Отдельно отмечу: тут не предполагается, что для всего, что кто-то сочтёт «определением числа», может быть построено число. Напротив, в данном способе нумерации только те числа, которые могут быть построены, сопоставляются определениям.
Предположим, что доказательство Кантора верно и у некоторых чисел не может быть номеров. В нашем способе нумерации сие будет означать, что таким числам гарантированно не сопоставлено никакое определение, то есть его у них нет.
Кантор для доказательства предъявляет именно такое число — такое, у которого гарантированно не будет номера, однако его, с точки зрения Кантора, всё равно можно построить при любом способе нумерации.
То есть в нашем способе нумерации Канторовское число будет одним из тех, у которых нет и не может быть определения. В частности, определения в виде конечного алгоритма построения, описанного на каком-либо языке.
С этого момента у нас остаётся всего три возможных варианта:
- Мы пришли к противоречию — определение «Канторовского числа» дано в виде конечного текста, однако из рассуждений следует, что такого текста не может быть.
- На самом деле, текст, которым описан процесс построения «Канторовского числа», только показался осмысленным — он не имеет смысла и никакого числа не определяет.
- При такой системе нумерации вещественные числа всё-таки можно занумеровать.
Все три варианта говорят о том, что доказательство Кантора не может быть верным.
Либо минимум одна из принятых предпосылок приводит к противоречию. Причём ей не является предположение о возможности занумеровать вещественные числа, поскольку замена оной на её отрицание всё равно приводит к противоречию — противоречиво ещё что-то, кроме неё. А потому система предпосылок противоречива, независимо от данного предположения, то есть мы не можем в ней доказать истинность или ложность предположения о возможности занумеровать вещественные числа.
Либо в доказательстве дан алгоритм построения, который на самом деле ничего не строит и не определяет, и, следовательно, по такой сущности нельзя сделать никаких логических выводов — в том числе, опровергнуть предположение о возможности занумеровать вещественные числа.
Либо утверждение о несуществовании способа нумерации неверно, поскольку минимум один такой способ есть (а реально есть целое множество таких способов, поскольку языков и алфавитов, подходящих для этих целей, существует весьма много, а построить их можно ещё больше).
Доказательство о неравномощности множества и множества всех его подмножеств взаимно однозначно сводимо к доказательству неравномощности натуральных и вещественных чисел, но мы можем даже этим не пользоваться — нам достаточно заменить в вышеприведённых рассуждениях «нумерацию вещественных чисел» на «нумерацию элементов множества всех подмножеств множества натуральных чисел» и прийти к тому же выводу, но теперь уже не про «Канторовское число», а про «Канторовское множество».
Фактически, оба Канторовских доказательства — «самоуничтожающиеся». То есть, если они верны, то из этого следует, что они не могут быть верны. Такое, надо отметить, встречается очень нечасто, а потому вполне понятно, почему это могли не замечать столь долго.
P.S. Что интересно, использованное в статье сопоставление всех чисел, у которых есть определения, этим числам — оверкилл. В том смысле, что для опровержения описанным тут способом достаточно было бы сопоставить определения числам только для тех чисел, определения которых нам известны.
Это не был бы способ нумерации всех вещественных чисел, однако если повторить изложенные в статье рассуждения для этого случая, то выяснится, что даже в его рамках Канторовское число не может иметь номера, а потому либо его определение в принципе не может быть нам известно, либо оно не может быть построено, поскольку процесс его построения внутренне противоречив. Разумеется, второе гораздо более осмысленно, чем первое, и означает, что Канторовское число возможно построить не во всех случаях, а лишь в некоторых, и, таким образом, опровергать общий случай оно не может.
doc-файл
Четвертый вариант:
На самом деле, текст, которым описан твой способ нумерации вещественных чисел только показался осмысленным — он не имеет смысла и никакого способа нумерации вещественных чисел не определяет.
> Либо минимум одна из принятых предпосылок приводит к противоречию.
И эта предпосылка — что в "множество определений" будет включен результат какого-то преобразования этого самого "множества определений".
Твоё "множество определений" определено рекурсивно.
Со времен парадокса Рассела, в теории множеств так делать нельзя, именно потому, что это приводит к противоречиям.
Это смелое предположение, в отличие от описанного в статье, основано ни на чём. Кроме него можно было бы также рассмотреть варианты: «так хочет Бог» и «потому что гладиолус», но мы, пожалуй, не будем.
> И эта предпосылка — что в "множество определений" будет включен результат какого-то преобразования этого самого "множества определений".
Если говорится «у нас получилось число», а до того говорится «мы его строим вот так-то», то этот текст должен быть определением числа, то есть присутствовать во множестве всех определений.
> Со времен парадокса Рассела, в теории множеств так делать нельзя, именно потому, что это приводит к противоречиям.
В парадоксе Рассела определялось множество, которое невозможно построить. При этом я совершенно согласен, что ни Канторовское множество, ни Канторовское число невозможно построить ровно по означенной мной причине. И с тем, что не любое множество/число, для которого можно написать что-то, что будет казаться кому-то его определением, можно построить, я тоже совершенно согласен. Вот, например, для Канторовских сабжей можно написать что-то кажущееся определением, и при этом построить их уже нельзя.
Если не вдаваться в детали, для доказательства того, что натуральных чисел бесконечно много, дается алгоритм построения натурального числа которого нет в произвольном конечном списке. А именно: берем максимальное число из списка и добавляем к нему 1.
Построение этого «числа» — ключевой момент доказательства, поскольку именно при помощи рассуждений об этом числе, вроде бы построенном на базе предположения о конечности множества натуральных чисел, опровергается это самое предположение и делается вывод, что верно обратное — то есть что множество натуральных чисел бесконечно.
Само по себе сие содержит логический изъян, поскольку для полноты доказательство недостаточно продемонстрировать, что некоторое предположение приводит к противоречию — кроме того, надо ещё доказать, что к противоречию не приводит отрицание этого предположения. Что совершенно не обязательно.
И сейчас будет как раз тот самый случай, когда отрицание предположения тоже приводит к противоречию.
Предположим, что доказательство верно и, таким образом, множество натуральных чисел бесконечно.
Теперь в качестве того самого, фигурирующего в доказательстве, «произвольного конечного списка» выберем вот такой: L = [max(L) + 1, 2, 3]
Предположим, что доказательство верно и у есть натуральное число, которого нет в списке. В нашем конечном списке сие будет означать, что такое число не находится в списке.
С этого момента у нас остаётся всего три возможных варианта:
1. Мы пришли к противоречию — max(L) + 1 не должно находиться в списке, однако оно там находится.
2. На самом деле, текст, которым описан процесс построения «числа, которого нет в конечном списке», только показался осмысленным — он не имеет смысла и никакого числа не определяет.
3. Такой список натуральных чисел всё таки содержит все натуральные числа.
Все варианты говорят о том, что доказательство бесконечности множества натуральных чисел не может быть верным.
Либо минимум одна из принятых предпосылок приводит к противоречию. Причём ей не является предположение о конечности множества натуральных чисел, поскольку замена оной на её отрицание всё равно приводит к противоречию — противоречиво ещё что-то, кроме неё. А потому система предпосылок противоречива, независимо от данного предположения, то есть мы не можем в ней доказать истинность или ложность предположения о конечности множества натуральных чисел.
Либо в доказательстве дан алгоритм построения, который на самом деле ничего не строит и не определяет, и, следовательно, по такой сущности нельзя сделать никаких логических выводов — в том числе, опровергнуть предположение о конечности множества натуральных чисел.
Либо утверждение о конечного списка, содержащего все натуральные числа неверно, поскольку минимум один такой список есть
Фактически, доказательство — «самоуничтожающееся». То есть, если оно верно, то из этого следует, что оно не может быть верно. Такое, надо отметить, встречается очень нечасто, а потому вполне понятно, почему это могли не замечать столь долго.
Edited at 2021-01-30 13:34 (UTC)
И, разумеется, я не считаю, что возможен список натуральных чисел — возможен только бесконечный генератор каждого следующего, ещё не встречавшегося числа.
Поэтому, ясен хер, max(list) + 1 на бесконечном генераторе никогда не завершит свою работу и ничего про «конечность» не докажет.
Edited at 2021-01-30 14:15 (UTC)
У меня обратный процесс: для каждого числа, проверяется, есть ли у него определение, и если есть, именно им нумеруется это число.
Edited at 2021-01-30 15:28 (UTC)
На данное опровержение это никак не влияет. Признавать «существующим» нечто, у чего в принципе нет определения, включая алгоритм построения или определение через «является ответом некоторой задачи», да и вообще никак не может быть обнаружено, уже очень странно, поскольку слово «существует» после этого перестаёт означать что-либо осмысленное, однако для опровержения достаточно того, что конкретно Канторовское число не может иметь определения по своему построению, а следовательно не может иметь и алгоритма построения.
Например, мы не можем при помощи алгоритма перенумеровать все алгоритмы, останавливающиеся на произвольном входе, хотя множество таких алгоритмов счётно. Соответственно мы не можем перенумеровать множество вычислимых чисел, оно не перечислимо.
Если множество не перечислимо, то диагональный метод всё равно работает, но вот алгоритма для него уже не существует. Потому что мы можем сказать "возьмём цифру, отличающуюся от N-ной цифры N-ного алгоритма, если он останавливается на любом входе, или 0, если не останавливается". Это будет вполне строгое и конечное определение числа, но вот написать алгоритм, который генерирует такое число, мы не сможем. Это будет пример определимого (definable), но невычислимого (uncomputable) числа.
Любой конечный текст — это уже натуральное число.
> что любому определению соответствует натуральное число
Действительно, а что если среди натуральных чисел есть фрагмент, который нельзя перенумеровать? Это же тогда получится, что и некоторое подмножество натуральных чисел несчётно!
Edited at 2021-02-05 00:14 (UTC)
Нет. Вещественное число это не конечное число, а бесконечная последовательность цифр. Например, 0,333..
Дадим всем вещественным числам определения.
У числа 0,33.. определение будет "число 0,33..".
Это определение бесконечно.
Получился континуум определений.
Можно выкинуть из этого континуума счётное число рациональных чисел. Потом счётное число чисел с периодом, таких как наше число 0,3(3). Алгебраические числа. И т.д., кучу счётных множеств по любым правилам, которые нам придут в голову. Эту всю совокупность счётных множеств можно занумеровать конечными определениями.
И всё равно останется континуум вещественных чисел и их соответствующих бесконечных определений.
Т.е. всё равно останутся бесконечные последовательности после запятой, которые не уложились ни в один из наших алгоритмов.
Для простоты положим, что мы никакие счётные последовательности не выкидывали. И возьмем только вещественные числа от 0 до 1.
Пусть мы нумеруем числа по разрядам
0,1 .. 0,9; 0,10 .. 0,99 (выкидывая посчитанные числа с одним знаком после запятой); 0,110 .. 0,999 и т.д.
При таком способе нумерации мы никогда не доберемся до числа 0,3(3)
Выберем какую-нибудь другую нумерацию. Тогда мы не доберемся до канторового числа, которое соответствует этой нумерации.
Отлично! Тогда мы по предложенному тобой алгоритму занумеруем числа так:
1. "Число, которое при данном способе нумерации соответсвует канторовому числу"
2. "Число x,xxx"
3. "Число y,yyy"
..
А теперь давай сопоставим каждому определению число.
1. "тэкс, посмотрим.. если бы у нас были только числа начиная с п. 2, то мы бы знали канторовое число. Но у нас есть п. 1, учёт которого даёт новое канторовское число. Как же его вычислить? Нам нужно найти число из п. 1, остальные числа мы знаем. Ну, ищем по определению. Читаем 'число, которое при данном способе нумерации..'. Тэкс, а какой у нас способ нумерации?
Ага '1 "Число, которое при данном способе нумерации.."'. Ищем его.
Вот и зациклились, как и писали люди в предыдущих комментариях.
Т.е. определению "Число, которое при данном способе нумерации соответсвует канторовому числу" не соотвествует никакое число, и это определение выкидывается из множества определений. Выкидывается так же, как любой бессмысленный набор слов.
У числа (и у чего-либо другого) не может быть бесконечного определения, поскольку в этом случае невозможно будет воспользоваться этим определением, то есть проверить сущность на соответствие или несоответствие определению. Тем самым, такое «определение» не будет определением.
> Т.е. определению "Число, которое при данном способе нумерации соответсвует канторовому числу" не соотвествует никакое число, и это определение выкидывается из множества определений.
https://lex-kravetski.livejournal.com/685801.html