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

[mihailm]

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

...ПРОЦЕСС ПОСТРОЕНИЯ нашего числа НЕ ЗАВЕРШИТСЯ НИКОГДА...

Тогда у вас много чего в математике никогда не завершится - пределы например, ну нет предела, этож операция с бесконечным множеством.
И без числа $\pi$ останетесь - вобщем куцая у вас математика будет)
А нам мозги не парьте пож-та - у вас своя "математика", у нас своя МАТЕМАТИКА, по доброму разойдемся?

[Мастак]

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

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

а ПРОЦЕСС ПОСТРОЕНИЯ нашего числа НЕ ЗАВЕРШИТСЯ НИКОГДА.

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

У действительных чисел есть конструктивные представления, какими можно оперировать. Но мы не имеем права утверждать ничего о том, какая цифра в представлении числа $\pi$ в $10^{10}$ знаке после запятой, пока не вычислим конкретно (а в доказательстве как раз такие утверждения). Хотя и у числа $\pi$ есть разные конструктивные представления.

[Nemiroff]

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

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

Ну да, помечтайте.

А пока мечтаете, мне ответьте.

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

Согласны с доказательством? Если есть ошибка --- в какой строке?

[Xaositect]

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

У действительных чисел есть конструктивные представления, какими можно оперировать. Но мы не имеем права утверждать ничего о том, какая цифра в представлении числа $\pi$ в $10^{10}$ знаке после запятой, пока не вычислим конкретно (а в доказательстве как раз такие утверждения). Хотя и у числа $\pi$ есть разные конструктивные представления.

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

[Someone]

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

Вопрос простой: если мы записали ВСЕ (!) числа из интервала (0,1),
то как вообще мы смогли "записать" ЕЩЕ ОДНО ЧИСЛО, по определению, данному раньше, ИЗ ЭТОГО ЖЕ ИНТЕРВАЛА?

Мы просто предположили, что исхитрились как-то перечислить все числа из интервала $(0,1)$. Последующее рассуждение показало, что наше предположение неверно.
Кстати, это предположение вообще для доказательства не нужно. И сам Кантор, кстати, эту теорему доказывал без такого предположения и без диагонального метода. Изложение этого доказательства можно найти в сообщении http://dxdy.ru/post414177.html#p414177. Предварительно следует очень внимательно разобрать сообщение http://dxdy.ru/post413407.html#p413407.

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

ПРОЦЕСС ПОСТРОЕНИЯ нашего числа НЕ ЗАВЕРШИТСЯ НИКОГДА.

Нету тут никакого процесса. Раз уж Вы умеете вычислять $a_{n,k}$ для любых натуральных $n,k$, то кто может помешать Вам вычислить

$$b_n=\begin{cases}1\text{, если }a_{n,n}\neq 1,\\ 2\text{, если }a_{n,n}=1?\end{cases}$$

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

Но мы не имеем права утверждать ничего о том, какая цифра в представлении числа $\pi$ в $10^{10}$ знаке после запятой, пока не вычислим конкретно (а в доказательстве как раз такие утверждения)

А для доказательства абсолютно по фигу, какая там цифра "конкретно". Какая-то цифра есть, и этого достаточно.

[nikvic]

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

У действительных чисел есть конструктивные представления, какими можно оперировать. Но мы не имеем права утверждать ничего о том, какая цифра в представлении числа $\pi$ в $10^{10}$ знаке после запятой, пока не вычислим конкретно (а в доказательстве как раз такие утверждения).

С числом $\pi$ это так. Однако стандартные конструктивные представления не позволяют, вообще говоря, вычислить цифру разложения.

[Мастак]

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

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

Вопрос простой: если мы записали ВСЕ (!) числа из интервала (0,1), то как вообще мы смогли "записать" ЕЩЕ ОДНО ЧИСЛО, по определению, данному раньше, ИЗ ЭТОГО ЖЕ ИНТЕРВАЛА?
Какой еще ответ может быть, кроме такого, что мы строили это число некорректно, то есть наши операции (а точнее операции "диагонального метода Кантора") при построении были некорректны?

Мням. А давайте так:
$\eqno (0.1)$ Пусть $X$ --- произвольное множество, $\mathcal{P}(X)$ --- множество всех подмножеств $X$.
$\eqno (0.2)$ Пусть $f$ --- биекция $X$ на $\mathcal{P}(X)$. Требуется доказать или опровергнуть её существование.
$\eqno (1)$ Пусть $Y = \{ x \in X : x \not\in f(x) \} $.
$\eqno (2)$ $f$ --- биекция, потому $Y = f(y)$ для некоторого $y \in X$.
$\eqno (3)$ Если $y \in Y$, то $y \in f(y)$ и $y \not\in Y$.
$\eqno (4)$ Если $y \not\in Y$, то $y \not\in f(y)$ и $y \in Y$.
$\eqno (5)$ Противоречие --- $f$ не существует.

Согласны с доказательством? Если есть ошибка --- в какой строке?

Мы в доказательстве предположили, что существует биекция $f$, и вопрос в том: а на каком основании мы утверждаем, что сможем построить множество $Y$.
PS И возможный ответ - на основании аксиомы выделения, которые парадоксальны. Неконструктивность "спряталась" за аксиомы. Но, как минимум, при доказательстве надо бы аксиомы упомянуть и сказать,
что мы считаем их справедливыми вообще.

[Nemiroff]

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

Мы в доказательстве предположили, что существует биекция $f$, и вопрос в том: а на каком основании мы утверждаем, что сможем построить множество $Y$.

То есть, проблема в строке а номером 1?

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

на основании аксиомы выделения или аксиомы выбора, которые парадоксальны. Неконструктивность "спряталась" за аксиомы.

Вам аксиомы не нравятся? Без них гораздо хуже.

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

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

Я пока предполагаю вас мыслящим субъектом. Так что некоторые вещи отдаю на откуп без дополнительных уточнений.

[Someone]

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

PS И возможный ответ - на основании аксиомы выделения или аксиомы выбора, которые парадоксальны. Неконструктивность "спряталась" за аксиомы. Но, как минимум, при доказательстве надо бы аксиомы упомянуть и сказать,
что мы считаем их справедливыми вообще.

Аксиома выбора здесь вообще ни при чём. Аксиома выделения используется. Ваше пожелание "аксиомы упомянуть и сказать" сильно запоздало, поскольку у математиков не принято доказывать теоремы, не указав явно всё, что требуется для доказательства. Другое дело, что нужно быть идиотом, чтобы каждый раз перечислять все аксиомы. Если уж Вы изучаете теорию множеств, Вы должны знать список аксиом изучаемой теории и список используемых в данной теории логических аксиом и правил вывода. Насчёт "справедливости вообще" не знаю, что и сказать. Что это за зверь? Если в теории есть какая-то аксиома, то в этой теории аксиома считается справедливой. В другой теории этой аксиомы может не быть, и там она не обязана быть справедливой. А что значит "справедлива вообще"?

В действительности ZFC — это просто формализация общепринятых методов доказательства. В частности, "парадоксальная" аксиома выделения, до сих пор не породившая ни одного парадокса, встречается на каждом шагу. Например, когда школьник говорит об области определения функции, он, не зная об этом, пользуется аксиомой выделения. А упоминая множество значений функции, не обходится без аксиомы подстановки.

[Мастак]

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

Вам аксиомы не нравятся? Без них гораздо хуже.

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

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

... некоторые вещи отдаю на откуп без дополнительных уточнений.

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

[Someone]

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

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

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

[Xaositect]

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

Множество функций из $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$;

[Nemiroff]

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

следующего $ \forall a \exist!c \forall b \ ( b \in c \leftrightarrow b \in a \ \land \ b \notin c \ )$

Что есть восклицательный знак?
А, я понял, вы квантор потеряли из-за отсутствия пробела почти.

[Мастак]

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

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

PS И возможный ответ - на основании аксиомы выделения или аксиомы выбора, которые парадоксальны. Неконструктивность "спряталась" за аксиомы. Но, как минимум, при доказательстве надо бы аксиомы упомянуть и сказать,
что мы считаем их справедливыми вообще.

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

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

[Xaositect]

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

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

У Вас квантор неправильно набран, надо \exists.
Нет, аксиома выделения не позволяет утверждать то, что Вы написали. Там в выделяющую формулу не может $c$ входить свободно