Краткая форма опровержения доказательств Кантора

[lex_kravetski]

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

Comments

[ichthuss]

Мнжно написать еще короче: "наименьшее из натуральных чисел, которое нельзя определить текстом на русском языке длиной не более 120 символов". С этим определением ровно та же проблема, что и с твоим "канторовским числом", только безо всякого Кантора. Проблема не в Канторе, а в естественном языке - он недостаточно формален, чтобы подобные высказывания могли сойти за математически строгий предикат.

[lex_kravetski]

У меня нет предположения о том, что для всего, что кто-то сочтёт «определением», обязательно может быть построено число.

У меня обратный процесс: для каждого числа, проверяется, есть ли у него определение, и если есть, именно им нумеруется это число.

[ichthuss]

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

[lex_kravetski]

> Так с точки зрения математики разницы нет, это один и тот же процесс

[ichthuss]

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

[lex_kravetski]

> "Любой способ идентификации" - это бессмысленный набор букв.

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

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

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

[ichthuss]

Точно так же бессмысленный. Потому что вокруг этого "определения" точно так же можно элементарно накрутить ровно такой же парадокс. Соответственно, эта русская фраза не может служить определением в математическом смысле слова. Так же, как, например, русская фраза "множество всех множеств".

[lex_kravetski]

Вокруг какого-то можно, однако фишка, что описанное в статье выполняется для абсолютно любого способа.

[eldies]

> описанное в статье выполняется для абсолютно любого способа.

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

Тогда твоё
в нашем способе нумерации Канторовское число будет одним из тех, у которых нет и не может быть определения
Превращается в
в нашем способе нумерации Канторовское число ("число, полученное применением канторовской процедуры к некой нумерации "множества определений"") будет одним из тех, у которых нет и не может быть определения, не ссылающегося на "множество определений"

Ой, больше нет никакого противоречия, "опровержение" рассыпалось, описанное в статье не выполняется.

Невероятно: стоит убрать рекурсивность из твоих построений, и "опровержение" больше не работает.

[ichthuss]

Нет, описанное в статье не работает ни для одного _корректного_ (т.е. однозначного и непротиворечивого) способа очертить "множество определений". Можешь попробовать привести контрпример.

[lex_kravetski]

Любое определение - текст. Любой текст - автоматически номер.

[ichthuss]

Однако нам не годится любое определение. Нам нужны только те определения, которые реально определяют некоторую бесконечную десятичную дробь, чтобы можно было получить i-й знак этой дроби. А в этой фильтрации вся собака-то и зарыта. Без нее мы не можем построить диагональную дробь, т.к. не все цифры на нашей главной диагонали определены. А с этой фильтрацией полученное число будет корректным, но будет этим самым фильтром отфильтровано. Проверь сам - предложи любой конкретный способ фильтрации.

[lex_kravetski]

> Нам нужны только те определения, которые реально определяют некоторую бесконечную десятичную дробь, чтобы можно было получить i-й знак этой дроби.

Любую нумерацию можно перенумеровать без пропусков.

> Проверь сам - предложи любой конкретный способ фильтрации.

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

[ichthuss]

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

[lex_kravetski]

> Например, для описания "число, составленной по методу диагонального аргумента из последовательности, отфильтрованной данным способом" он не может дать ни положительного, ни отрицательного ответа.

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

[ichthuss]

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