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

[Мастак]

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

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

хм, так, применяя аксиому формально, мы допускаем справедливость
следующего $ \forall a \exists !c \forall b \ ( b \in c \leftrightarrow b \in a \ \land \ b \notin c \ )$

Подробнее, пожалуйста. Ничего же непонятно.

это формальное (без интерпретации смысла $\Phi[b]$) применение аксиомы выделения
$ \forall a \exists !c \forall b \ ( b \in c \leftrightarrow b \in a \ \land \ \Phi[b]\ )$

[Nemiroff]

Мастак, а вы принципиально на последнее сообщение на странице сразу не отвечаете?
Xaositect всё написал вам.

[Мастак]

Nemiroff в сообщении #822002 писал(а):

Мастак, а вы принципиально на последнее сообщение на странице сразу не отвечаете?
Xaositect всё написал вам.

отвечу, отвлекли срочные мелкие дела

[Someone]

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

Мне показалось, что на основании аксиомы выбора возможно построить $Y$ из примера.

Какой "$Y$ из примера"? Из какого "примера"?

Если Вы про формулу (1) из http://dxdy.ru/post821966.html#p821966, то там явная аксиома выделения: конструкция $\{x:x\in A\wedge\Phi(x)\}$ определяется как раз с помощью аксиомы выделения.

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

это формальное (без интерпретации смысла $\Phi[b]$) применение аксиомы выделения
$ \forall a \exists !c \forall b \ ( b \in c \leftrightarrow b \in a \ \land \ \Phi[b]\ )$

И как Вы её применяете?

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

Множество функций из $A$ в $B$ будем обозначать $A\to B$.

Ой, какое неудачное обозначение. Множество функций из $A$ в $B$ обычно обозначается $B^A$. А ваше обозначение провоцирует путаницу.

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

Доказательство. От противного.

Господи, далось всем это "от противного". Там же в рассуждении ни инъективность, ни сюръективность $F$ никак не используется.

[Мастак]

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

Так, мы поняли, что Вам не нравится аксиома выделения. Не хотите - не надо, аналог теоремы Кантора можно даже в простой теории типов доказать.

Множество функций из $A$ в $B$ будем обозначать $A\to B$. Множество из двух элементов обозначим $\mathbf{2}$, на нем введем функцию $\mathrm{not}$, которая элементы переставляет. Вместо подмножеств будем рассматривать их характеристические функции, т.е. элементы $A\to \mathbf{2}$

Теорема. $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}$, которая каждому элементу $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)$.

В этом доказательстве Вам какие аксиомы не нравятся? Их тут немного: 1) существование множества $\mathbf{2}$ и функции $\mathrm{not}$; 2) метод доказательства от противного; 3) Если $f\in A\to B$ и $a\in A$, то существует $f(a)\in B$; 4) Вычисление по формуле ($\lambda$ - абстракция): если $z$ --- переменная типа $A$ и $\phi[z]$ --- формула с этой переменной, то существует функция, сопоставляющая каждому $z\in A$ значение формулы $\phi$ на этом $z$;

Интерпретация: формулировка эквивалентна другим формулировкам теоремы Кантора (хотя наверно лучше не "меньше", а "не равномощно"). Доказываем от противного. И наверно предполагаем существование биекции F.
И здесь

Цитата:

Рассмотрим функцию $\chi\in A\to\mathbf{2}$, которая каждому элементу $z\in A$ сопоставляет значение $\mathrm{not} (F(z)(z))$.

, и здесь опять "диагональный метод Кантора", то есть по $z$ находим функцию $F(z)$, вычисляем $F(z)(z)$ и меняем значние $F(z)(z)$ на другой элемент из $\mathbf{2}$, и не можем закончить процесс, так как, если остановимся на некотором шаге, то всегда найдутся в $ F(x)$ функции, реализующие такие же отображения для тех элементов из $A$, какие мы успели рассмотреть, а $F$ - биекция, то есть корректность построения не гарантирована.
Контекст правильно проинтерпретирован?

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

PS В чём "претензии" к "диагональному методу Кантора"? Это как начать
перебирать натуральные числа, утверждая, что мы можем найти число, которое
не будет принадлежать множеству натуральных чисел только потому, что
мы его пока еще не успели перебрать.

[Nemiroff]

Я так и не понял, вам аксиома выделения не нравится или что? Или неконструктивность?

[Мастак]

Nemiroff в сообщении #822202 писал(а):

Я так и не понял, вам аксиома выделения не нравится или что? Или неконструктивность?

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

[Someone]

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

Аксиома выделения не исключает парадоксы

Что значит — "не исключает"? Она их должна законодательно запрещать, или как? Достаточно того, что она их не создаёт. Попробуйте предъявить хотя бы один парадокс, созданный аксиомой выделения.

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

"диагональный метод Кантора" неконструктивен

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

[Xaositect]

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

Контекст правильно проинтерпретирован?

Да, это диагональный метод.

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

PS В чём "претензии" к "диагональному методу Кантора"? Это как начать
перебирать натуральные числа, утверждая, что мы можем найти число, которое
не будет принадлежать множеству натуральных чисел только потому, что
мы его пока еще не успели перебрать.

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

"диагональный метод Кантора" неконструктивен.

Никакого перебора в моем доказательстве нет. Я перечислил аксиомы, которые используются. Какая из них Вам не нравится? Более того, я его переписал с формального доказательства для компьютера, которое конструктивнее некуда: для каждой функции $F$ нужного типа строит доказательство противоречия $0 = 1$.

[Someone]

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

Никакого перебора в моем доказательстве нет.

В диагональном методе нет ни перебора, ни "процесса". Мастак просто игнорирует то, что ему говорят. Если это продолжится, тему можно будет отправить в Пургаторий, тем более, что обсуждалась она много-много раз. Поиск в разделе "Дискуссионные темы (М)" даёт 27 тем, в которых упоминается одно из сочетаний слов "теорема Кантора", "теорему Кантора", "теоремы Кантора", "теореме Кантора" (именно в таких грамматических формах). Не все 27 посвящены именно обсуждаемой теореме, но и далеко не одна.

[Duku]

Для любой явно предъявленной таблицы всегда можно предъявить не включенное в нее диагональное число, но и для любого явно предъявленного диагонального числа существует таблица, в котором оно занумеровано.
Степень убедительности обоих подходов, примерно одинакова.
К примеру,
$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}$

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

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

[Xaositect]

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

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

Это верно, никак не противоречит друг другу, прекрасно соответствует большинству теорий множеств и похожих на них вещей от ZFC до HoTT, и никаких споров среди математиков не вызывает. Математик, если хочет рассматривать теорию множеств без теоремы Кантора, так и говорит - давайте рассмотрим теорию с аксиомами такими-то и без аксиом таких-то, и доказывает, что теоремы Кантора вывести нельзя (скорее всего, огромная куча полезных результатов при этом отправляется в ту же сторону, куда и теорема Кантора).

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

К примеру,
$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}$

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

И таким образом, в таблице оказываются только числа вида $\frac{m}{10^k}$, а, например, $\frac{1}{3}$ не нумеруется.

[Sonic86]

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}...............................$ (обратите внимание на многоточие)

[Someone]

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

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

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

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

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

Не встречал никаких споров на этот счёт среди профессиональных математиков. Среди неучей — да, споров много. Вот и сюда вылезают со своими спорами.
Кроме того, я не понимаю, что такое "канторовский метод" и кто его навязывает. Вы намекаете на мировой заговор?

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

Степень убедительности обоих подходов, примерно одинакова.

Каких "обоих"?

[Мастак]

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

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

Аксиома выделения не исключает парадоксы

Что значит — "не исключает"? Она их должна законодательно запрещать, или как? Достаточно того, что она их не создаёт. Попробуйте предъявить хотя бы один парадокс, созданный аксиомой выделения.

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

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

-- Вт фев 04, 2014 11:41:09 --

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

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

Контекст правильно проинтерпретирован?

Да, это диагональный метод.

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

PS В чём "претензии" к "диагональному методу Кантора"? Это как начать
перебирать натуральные числа, утверждая, что мы можем найти число, которое
не будет принадлежать множеству натуральных чисел только потому, что
мы его пока еще не успели перебрать.

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

"диагональный метод Кантора" неконструктивен.

Никакого перебора в моем доказательстве нет. Я перечислил аксиомы, которые используются. Какая из них Вам не нравится? Более того, я его переписал с формального доказательства для компьютера, которое конструктивнее некуда: для каждой функции $F$ нужного типа строит доказательство противоречия $0 = 1$.

Ведь наша $\chi$ определяется как процесс (и этот процесс упорядочен не более порядка в переборе). Отвечая и Someone - под конструктивностью понимают всякое, но в общем (или только в общем философском понимании) аналогичное. Здесь похоже на

Цитата:

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

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