Доказательство теоремы Кантора некорректно

[Xaositect]

Мастак в сообщении #822560 писал(а):

есть алгоритм построения и алгоритм
реализован формально (просто записали и синтаксических ошибок нет, технических runtime-ошибок нет, то есть программа запускается и работает на каких-то тестах, но ничего не знаем про логические runtime-ошибки) некоторой компьютерной программой.

Именно так и реализована у меня $\chi$. Мы ведь предполагаем существование сюрьекции $F$, то есть, раз уж мы конструктивисты, предполагаем существование программы $F$, которая по номеру строки $x$ выдает нам программу вычисления последовательсти $F(x)$. Вот в терминах этой $F$ мы и реализуем $\chi(x) = not(F(x)(x))$.

[Мастак]

Xaositect в сообщении #822564 писал(а):

Мастак в сообщении #822560 писал(а):

есть алгоритм построения и алгоритм
реализован формально (просто записали и синтаксических ошибок нет, технических runtime-ошибок нет, то есть программа запускается и работает на каких-то тестах, но ничего не знаем про логические runtime-ошибки) некоторой компьютерной программой.

Именно так и реализована у меня $\chi$. Мы ведь предполагаем существование инъекции $F$, то есть, раз уж мы конструктивисты, предполагаем существование программы $F$, которая по номеру строки $x$ выдает нам программу вычисления последовательсти $F(x)$. Вот в терминах этой $F$ мы и реализуем $\chi(x) = not(F(x)(x))$.

По номеру строки, где записан один элемент $x$ из $A$, причем строк может быть счетное количество (пока ладно - лишь потенциально бесконечно, что допускает конструктивизм вообще), и наша программа $ F$ сперва делает поиск (выбор) из потенциально бесконечно множества функций и далее выполняет вычисление этой функции в точке $x$.

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

То есть такой программы $F$, ОСУЩЕСТВЛЯЮЩЕЙ ТРЕБУЕМОЕ, быть не может или она для каких-то очередных входных данных не остановится В АКТУАЛЬНОЕ ВРЕМЯ (пока результат программы еще будет нужен 8)). Либо F реализует построение каждый раз такой функции, при этом F может потенциально построить ВСЕ функции, отображающие все элементы из A во множество всех
функций $A\to\mathbf{2}$.

[Xaositect]

Нет, если уж хотите конструктивизм, то давайте разбираться, что Вы имеете в виду.

Давайте пока рассмотрим $A = \mathbb{N}$ --- натуральные числа. Надеюсь, в их конструктивности сомнений нет.
Тогда $A\to \mathbf{2}$ --- это последовательности, то есть функции, которые принимают натуральное число и выдают один бит. Для того, чтобы задать задать такую функцию конструктивно, нужно написать программу. Например, функция

bit f(nat x) { if (x % 2 == 1) return 1; else return 0; }

(воображаемый C-подобный язык) задает последовательность чередующихся нулей и единиц.
Тип $A\to (A\to \mathbf{2})$ - это тип той самой таблицы. Для каждого натурального числа мы должны узнать, как генерировать последовательность с этим номером. Для того, чтобы конструктивно задать такую таблицу $F$, нужно написать программу, которая принимает натуральное число $x$ и возвращает текст программы, задающей последовательность $F(x)$. Например, можно задать таблицу, у которой ниже главной диагонали единицы, а не ниже - нули:

program F(nat x) { return sprintf("bit f(nat x) { if (x < %d) return 1; else return 0; }", x); }

.

Согласны ли Вы с этим?

[Мастак]

Xaositect в сообщении #822578 писал(а):

Нет, если уж хотите конструктивизм, то давайте разбираться, что Вы имеете в виду.

Давайте пока рассмотрим $A = \mathbb{N}$ --- натуральные числа. Надеюсь, в их конструктивности сомнений нет.
Тогда $A\to \mathbf{2}$ --- это последовательности, то есть функции, которые принимают натуральное число и выдают один бит. Для того, чтобы задать задать такую функцию конструктивно, нужно написать программу. Например, функция

bit f(nat x) { if (x % 2 == 1) return 1; else return 0; }

(воображаемый C-подобный язык) задает последовательность чередующихся нулей и единиц.
Тип $A\to (A\to \mathbf{2})$ - это тип той самой таблицы. Для каждого натурального числа мы должны узнать, как генерировать последовательность с этим номером. Для того, чтобы конструктивно задать такую таблицу $F$, нужно написать программу, которая принимает натуральное число $x$ и возвращает текст программы, задающей последовательность $F(x)$. Например, можно задать таблицу, у которой ниже главной диагонали единицы, а не ниже - нули:

program F(nat x) { return sprintf("bit f(nat x) { if (x < %d) return 1; else return 0; }", x); }

.

Согласны ли Вы с этим?

нет
Мы должны уметь генерировать на одну из функций $A\to \mathbf{2}$, а все возможные.
PS Но это еще пока конструктивно возможно, то есть по очередному натуральному , как видится, сможем алгоритмически построить неповторяющую ни одну из тех, что были ранее, цепочку 0 и1 (в общем бесконечную). Что далее - пока без комментария.

PS Предлагаю освоить Haskell (если еще не освоен). Красивые понятные записи, математикоподобные записи задания типов, лямбда-выражения as-is, возможность работать с условными бесконечностями (!), ...

[Xaositect]

Хотите Haskell - будет Haskell

data Bit = O | I deriving Eq
data Nat = Z | S !Nat

Что Вы имеете в виду под тем, что генерировать надо не одну функцию, а все? В Haskell функция типа Nat->Nat->Bit при применении к одному аргументу типа Nat выдает одну функцию типа Nat->Bit. Например, а функция, которую я имел в виду в предыдущем посте, будет выглядеть так:

F x y = if y < x then I else O

или, если явно выделить то, что нас интересует результат частичного применения,

F x = \y -> if y < x then I else O

Утверждение же теоремы Кантора состоит в том, что нет такой функции типа Nat->Nat->Bit, образ которой содержал бы все функции типа Nat->Bit, то есть для любой функции F :: Nat->Nat->Bit, которая не редуцируется в (_|_) ни при каких значениях аргументов, найдется функция g:Nat->Bit, которая не совпадает с F n ни при каком n. Более того, по номеру строки n можно вычислить индекс ix n, на котором g не совпадает с F n.

Т.е. по функции F :: Nat -> Nat -> Bit можно определить фунции g :: Nat -> Bit и ix :: Nat -> Nat так, что можно доказать, что F n (ix n) == g n есть False для любого n :: Nat

g n = if (F n n == I) then O else I

ix = id

[Someone]

Мастак в сообщении #822583 писал(а):

нет
Мы должны уметь генерировать на одну из функций $A\to \mathbf{2}$, а все возможные.

Нам не нужно генерировать все возможные функции. У нас ситуация следующая: если мы хотим конструктивности, то наш список функций (который типа $A\to (A\to \mathbf{2})$) должен быть задан конструктивно: в виде алгоритма (функции), который, получив на входе натуральное число $n$, на выходе выдаёт функцию (типа $A\to\mathbf{2}$), которая в нашем списке имеет номер $n$. Подставляя в качестве $n$ натуральные числа $1,2,3,\ldots$, мы получим все функции из нашего списка. Функции, не входящие в список, нам не нужны. С точки зрения зрения конструктивизма задание списка функций означает именно это.

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

[Duku]

Если функция $\chi$ конструктивна, то ее можно внести в список нужных нам конструктивных функций $A\to (A\to2)$ и присвоить номер.
Если это не удается, алгоритм выдает ошибку или не останавливается, значит, она не конструктивная (или некорректная).
Задача аналогична разрешению вопроса, должен ли бриться брадобрей.

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

Sonic86 в сообщении #822398 писал(а):

Duku в сообщении #822376 писал(а):

Присвоим диагональному числу $x=b_{11}, b_{22}, b_{33}, b_{44}…b_{nn}$, где $b_{nn} \neq a_{nn}$ номер: $x_{n+1}= x$.

Нет никакого диагонального числа $x=b_{11}, b_{22}, b_{33}, b_{44}…b_{nn}$. Есть диагональное число $x=b_{11}, b_{22}, b_{33}, b_{44}…b_{nn}b_{n+1,n+1}...............................$ (обратите внимание на многоточие)

$x_1=a_{11}, a_{12}, a_{13},a_{14}…a_{1n}$
$x_2=a_{21}, a_{22}, a_{23}, a_{24}…a_{2n}$
$x_3=a_{31}, a_{32}, a_{33},a_{34}…a_{3n}$
$x_4=a_{41}, a_{42}, a_{43}, a_{44}…a_{4n}$
…
$x_{n+1}=a_{(n+1)1}, a_{(n+1)2}, a_{(n+1)3}…a_{(n+1)n}$
…
…………………………………………………………………… (это тоже многоточие)

Xaositect в сообщении #822384 писал(а):

Duku в сообщении #822376 писал(а):

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

Это верно, никак не противоречит друг другу…

Благодарю, я удовлетворен.

Xaositect в сообщении #822384 писал(а):

прекрасно соответствует большинству теорий множеств и похожих на них вещей от ZFC до HoTT

Много ли их ?

[Nemiroff]

Мастак в сообщении #822560 писал(а):

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

Пример - парадокс Рассела, и к качестве его представителя - парадокс брадобрея далее. Предположим, что брадобрей бреет тех, и только тех жителей города, которые не бреются сами. (Подразумевается, что жителями города являются только бреющиеся мужчины). Вопрос: кто бреет брадобрея?
Условия, кого бреет брадобрей, вполне записываются в виде аксиомы выделения.

А если более формально? Что за парадокс?
Я предоставил доказательство теоремы Кантора. На вопрос о некорректности получил какие-то отмазки вроде "аксиома тут что-то не совсем того".

Duku в сообщении #822636 писал(а):

Благодарю, я удовлетворен.

Только это "верно" никак не связано с теоремой Кантора. В данном конкретном случае --- с несчётностью множества действительных чисел.

[Someone]

Duku в сообщении #822636 писал(а):

Если функция $\chi$ конструктивна, то ее можно внести в список нужных нам конструктивных функций $A\to (A\to2)$ и присвоить номер.

Ну и что?
В связи с этим заявлением два вопроса к Вам:
1) понимаете ли Вы, что после внесения нового элемента в список получится другой список?
2) знаете ли Вы определение несчётного множества, и что в этом определении говорится про этот другой список?

Duku в сообщении #822636 писал(а):

$x_1=a_{11}, a_{12}, a_{13},a_{14}…a_{1n}$
$x_2=a_{21}, a_{22}, a_{23}, a_{24}…a_{2n}$
$x_3=a_{31}, a_{32}, a_{33},a_{34}…a_{3n}$
$x_4=a_{41}, a_{42}, a_{43}, a_{44}…a_{4n}$
…
$x_{n+1}=a_{(n+1)1}, a_{(n+1)2}, a_{(n+1)3}…a_{(n+1)n}$
…
…………………………………………………………………… (это тоже многоточие)

И что там с этим многоточием?

[Мастак]

Xaositect в сообщении #821991 писал(а):

Теорема. $A\to\mathbf{2}$ мощнее $A$, то есть не существует функции $F: A\to (A\to \mathbf{2})$ такой, что у каждого элемента $\chi\in A\to \mathbf{2}$ есть прообраз $x\in A$.
Доказательство. От противного. Предположим, что $F$ существует. Рассмотрим функцию $\chi\in A\to\mathbf{2}$, котораяt каждому элементу $z\in A$ сопоставляет значение $\mathrm{not} (F(z)(z))$. Пусть $a$ --- прообраз $\chi$, т.е. $F(a) = \chi$. Тогда $F(a)(a) = \chi(a) = \mathrm{not} (F(a)(a))$, что невозможно, так как для обоих элементов $p\in\mathbf{2}$ не выполняется $p = \mathrm{not}(p)$.

Суръекцию$ F$ бессмысленно же рассматривать, так как надо же доказать неравномощность, а если$ F$ суръекция, то (зачем вообще и) вправе взять из $A\to\mathbf{2}$ одну единственную функцию, то есть все отображения $F$ будут на неё. Потом рассматриваем некоторую \chi, у которой может и не быть прообраза, так как $F$ - у нас не биекция и вовсе не обязана для КАКОЙ-ТО$ \chi$ иметь прообраз в A.
Если же $\chi $- та наша одна функция, то мы при самом задании получаем парадокс - "Рассмотрим некоторый X, который - не X".
Когда всё же $F$ - биекция, то и тогда наше определение $\chi$ всё же ДОЛЖНО ИСКЛЮЧИТЬ порождение парадокса, а при задании $\ch$ мы обязательно для какого-то a встретимся с $F(a) = \ch$ и должны будет задавать $\ch$ как не-$\ch$ (нарушив, если хотите, аксиому исключённого третьего).

А если F - биекция, то "Мы должны уметь генерировать на одну из функций , а все возможные.".

[Xaositect]

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

Мастак в сообщении #822696 писал(а):

Когда всё же $F$ - биекция, то и тогда наше определение $\chi$ всё же ДОЛЖНО ИСКЛЮЧИТЬ порождение парадокса, а при задании $\ch$ мы обязательно для какого-то a встретимся с $F(a) = \ch$ и должны будет задавать $\ch$ как не-$\ch$ (нарушив, если хотите, аксиому исключённого третьего).

Да, и именно это и доказывает теорему Кантора. Если биекция существует, то мы получаем противоречие!

[Мастак]

Someone в сообщении #822590 писал(а):

Мастак в сообщении #822583 писал(а):

нет
Мы должны уметь генерировать на одну из функций $A\to \mathbf{2}$, а все возможные.

Нам не нужно генерировать все возможные функции. У нас ситуация следующая: если мы хотим конструктивности, то наш список функций (который типа $A\to (A\to \mathbf{2})$) должен быть задан конструктивно: в виде алгоритма (функции), который, получив на входе натуральное число $n$, на выходе выдаёт функцию (типа $A\to\mathbf{2}$), которая в нашем списке имеет номер $n$. Подставляя в качестве $n$ натуральные числа $1,2,3,\ldots$, мы получим все функции из нашего списка. Функции, не входящие в список, нам не нужны. С точки зрения зрения конструктивизма задание списка функций означает именно это.

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

В утверждении теоремы фигурируют именно все $A\to \mathbf{2}$ и уже написал - какой смысл рассматривать в качестве F сурьекцию (и что мы тогда собираемся доказать).
Не сомневаюсь (вместе с Вами) ни в конструктивности получения натуральных чисел, ни в конструктивности математических объектов, которые строит корректный алгоритм.
И если всё же мы будет рассматривать биекцию $F$, то мы должны иметь конструктивный (потенциально осуществимый) алгоритм, которые потенциально осуществимо строит все возможные функции $A\to \mathbf{2}$.
И тогда далее - пусть существует такой алгоритм $F$, который по любому натуральному n строит уникальную неповторимую функцию. И далее, как уже написал, при задании $ \chi$
мы должны проверять, а не определили ли мы уже её для какого-то $x$ (реализуя как бы аналог "диагонального метода"), либо надо доказать, что наша $ \chi$ не входит в наш потенциально составимый список значений F, а в F по определению входят все возможные функции.

-- Вт фев 04, 2014 18:49:00 --

Xaositect в сообщении #822724 писал(а):

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

Мастак в сообщении #822696 писал(а):

Когда всё же $F$ - биекция, то и тогда наше определение $\chi$ всё же ДОЛЖНО ИСКЛЮЧИТЬ порождение парадокса, а при задании $\ch$ мы обязательно для какого-то a встретимся с $F(a) = \ch$ и должны будет задавать $\ch$ как не-$\ch$ (нарушив, если хотите, аксиому исключённого третьего).

Да, и именно это и доказывает теорему Кантора. Если биекция существует, то мы получаем противоречие!

биекция = ( суръекция И инъекция )

У суръекции прообразы не обязаны быть единственными.

[Xaositect]

Мастак в сообщении #822726 писал(а):

У суръекции прообразы не обязаны быть единственными.

Именно. Но если мы доказали, что из существования сюрьекции выводится противоречие, то не существует сюрьекций, а значит, не существует и биекций.

[Мастак]

Xaositect в сообщении #822730 писал(а):

Мастак в сообщении #822726 писал(а):

У суръекции прообразы не обязаны быть единственными.

Именно. Но если мы доказали, что из существования сюрьекции выводится противоречие, то не существует сюрьекций, а значит, не существует и биекций.

И как соотносится существование или не существование суръекции с утверждением теоремы?

[Xaositect]

Мастак в сообщении #822734 писал(а):

И как соотносится существование или не существование суръекции с утверждением теоремы?

Вообще-то отсутствие сьюрьекций с $A$ на $B$ - это и есть определение термина "$B$ мощнее $A$".

Но если хочется, то можно так: если сюръекций не существует, то в частности, не существует и биекций, значит, множества $A$ и $2^A$ неравномощны.