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

[mihaild]

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

И если мы принимаем-признаем аксиому выбора, а ведь мы по умолчанию признали аксиому выбора, признав возможность построить $\beta$, то доказывать существование $\beta$ уже не надо. А если мы не признаем аксиому выбора, то должны тогда непосредственно вычислять-строить каждый элемент $\beta$,

Аксиома выбора тут не нужна. Тут нужна аксиома выделения.
Что такое последовательность? Это функция $\mathbb{N} \to A$, т.е. множество пар $\{\langle n, x\rangle|n \in \mathbb{N}, x \in A\}$ с определенными свойствами.
Нам принесли какую-то нумерацию $P$ последовательностей, т.е. функцию $\mathbb{N} \to (\mathbb{N} \to A)$. Мы строим последовательность $\beta$, не пронумерованную $P$, следующим образом:
1) берем множество всех пар $A^2 = N \times A$ (чтобы доказать его существование придется повозиться, но это делается)
2) строим множество $\beta$: $x \in \beta \leftrightarrow (x \in A^2 \wedge x_1 = 1 - P(x_0))$ - тут как раз используется аксиома выделения
3) доказываем, что $\beta$ - это последовательность, и $\forall n: P(n) \neq \beta$

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

[Мастак]

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

В общем, ввиду вашей злокачественной безграмотности в теории множеств, обсуждать с Вами доказательство теоремы Кантора совершенно бессмысленно.

Ваше "общее" мнение услышано, далее отвечать на Ваши посты в этом топике прекращу.
Глубокое же и широкое изучение матчасти всегда и всем полезно, хотя бы для
того, чтобы всем говорить на одном согласовано-грамотном языке.

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

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

А вот в отношении того, что можно и что нельзя делать с нумерациями, приведу цитату-описание одного "парадокса"

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

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

[atlakatl]

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

далее отвечать на Ваши посты в этом топике прекращу.

Someone уже третий, кто удостаивается такой чести в этом посте.

[Karan]

Мастак

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

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

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

1. Если дана последовательность последовательностей $\alpha$, всегда ли существует последовательность $\delta$ такая, что $\delta_i = \alpha_{ii}$?
2. Если дана последовательность $\delta$, всегда ли существует последовательность $\beta$ такая, что $\beta_i = 1 - \delta_i$?
3. Для указанных в вопросе 2 двух последовательностей $\delta$ и $\beta$ и конкретного числа $i$, является ли следующий текст доказательством $\delta_i \neq \beta_i$: "По определению $\beta$ имеем $\beta_{i} = 1 - \delta_i \neq \delta_i$?"
4. Если для двух последовательностей $\alpha$ и $\beta$ указан конкретный индекс $i$ и доказано, что $\alpha_i \neq \beta_i$, верно ли, что $\alpha \neq \beta$?
5. Если дана последовательность последовательностей $\alpha$ и последовательность $\beta$, и существует процедура (не использующая внутри бесконечных последовательностей, а использующая только одно конечное число, которое подается на вход), которая для любого индекса $i$ выдает индекс $j(i)$ и доказательство того, что $\alpha_{i, j(i)} \neq \beta_{j(i)}$, то верно ли, что $\alpha_i \neq \beta$ для любого $i$?

Вот, имхо, только в отношении пункта 5 пишу ответ "не согласен".

Таким образом, Ваши рассуждения ничего не говорят о некорректности теоремы Кантора в теории, которую обычно называют теорией множеств (ZFC).

Вы пользуетесь своей, необщепринятой теорией. Для того, чтобы вести обсуждение дальше, эту теорию надо определить так, чтобы все собеседники говорили об одном и том же. Тем не менее, Вы не ответили на вопрос Xaositect об уточнении Вашего понятия доказательства:

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

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

Я уточню этот вопрос. Наше утверждение имеет вид: для любой последовательности последовательностей бит $\alpha$ существует последовательность бит $\beta$ такая, что для любого индекса $i$ выполняется некоторое соотношение $\beta$ и $\alpha_i$ (В нашем случае, неравенство).
Понятно, что в $\beta$ в общем случае зависит от $\alpha$, то есть должна как-то строиться на основе $\alpha$. Вы признали некоторые такие построения (пункты 1-2 у Xaositect). Отсюда первый вопрос: какие построения возможны?
Если такое построение проведено, то из пунктов 3-4 из сообщения Xaositect можно сказать, что для конкретного заданного $i$ верно, что $\alpha_i \neq \beta$. Тем не менее, Вы отрицаете пункт 5, то есть Вы не считаете, что из этого следует для любого $i$. По сути, пункт 5 означает, что доказательство $\alpha_i \neq \beta$ может быть проведено компьютером автоматически для любого $i$, используя пункт 4. Тем не менее, Вы не признаете такое доказательства. Второй вопрос: какие способы доказательства Вы признаете? Можно ограничиться только утверждениями вида $\forall \alpha \exists \beta \forall i (\dots)$.

Как модератор, прошу Вас ответить на эти вопросы, иначе тема будет перенесена в Пургаторий как бессодержательная.

[gefest_md]

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

возникающий из-за некорректности модели объекта, рассматриваемого в доказательстве

О каком объекте Вы говорите? $\beta$? В его задании участвуют аксиома выделения (из $2^{\mathbb{N}\times\{0,1\}}$) и множество $X$ с его элементами.

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

Причем вот в таком доказательстве ведь "просматривается" упоминаемая выше функция выбора (, которая фигурирует во многих формулировках аксиомы выбора), задаваемая в пункте 2

В функции скорости $v=\frac{S}{t}$ тоже "просматривается" какой-то вариант аксиомы выбора, что ли? В пункте 2 доказательства по сути то же самое.

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

А бесконечные последовательности из 0 и 1 есть модель множества всех подмножеств некоторого бесконечного множества из элементов $a_k$

В доказательстве я не рассуждал по поводу, например, множества $2^\mathbb{N}$. Не было зачем.

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

Ведь $\beta$ входит во множество всех возможных последовательностей из 0 и 1, в "пересчёт некоторого бесконечного множества $X$ бесконечных последовательностей нулей и единиц: $\alpha(1),\ \alpha(2),\ \dots\ $".

В $X$ может и не входить то, что ищем ($\exists\beta$). Множество $X$ из моего доказательства - это не обязательно все последовательности.

[arseniiv]

(Оффтоп)

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

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

А результат-то противоположно-обратный получается. Ваше «глубокое и широкое» «изучение» приводит к тому, что вы изобретаете какую-то свою математику, интересную в итоге только вам. Остальным же ясно, что это велосипед с квадратными колёсами, и что вы не замечаете, что в ваших построениях недостаточно ясности.

[Karan]

Обсуждение, не относящееся к конкретным возражениям участника Мастак, выделено в тему "Кантор против Аристотеля"

[warlock66613]

(Оффтоп)

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

Укажите конкретного современного математика, отвергающего аксиому выбора. На конструктивистов прошу не ссылаться: в конструктивной математике аксиома выбора верна (в соответствующей формулировке).

А что, дескриптивная теория множеств (в которой, как известно, многие интересные результаты могут быть получены только из аксиомы детерменированности) для современной математики уже настолько неактуальна?

[Someone]

(warlock66613)

warlock66613 в сообщении #1249894 писал(а):

А что, дескриптивная теория множеств (в которой, как известно, многие интересные результаты могут быть получены только из аксиомы детерменированности) для современной математики уже настолько неактуальна?

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

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

Но давайте не будем развивать эту тему.

[Мастак]

Karan в сообщении #1248085 писал(а):

Тем не менее, Вы не ответили на вопрос Xaositect об уточнении Вашего понятия доказательства:

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

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

Я уточню этот вопрос. Наше утверждение имеет вид: для любой последовательности последовательностей бит $\alpha$ существует последовательность бит $\beta$ такая, что для любого индекса $i$ выполняется некоторое соотношение $\beta$ и $\alpha_i$ (В нашем случае, неравенство).
Понятно, что в $\beta$ в общем случае зависит от $\alpha$, то есть должна как-то строиться на основе $\alpha$. Вы признали некоторые такие построения (пункты 1-2 у Xaositect). Отсюда первый вопрос: какие построения возможны?
Если такое построение проведено, то из пунктов 3-4 из сообщения Xaositect можно сказать, что для конкретного заданного $i$ верно, что $\alpha_i \neq \beta$. Тем не менее, Вы отрицаете пункт 5, то есть Вы не считаете, что из этого следует для любого $i$. По сути, пункт 5 означает, что доказательство $\alpha_i \neq \beta$ может быть проведено компьютером автоматически для любого $i$, используя пункт 4. Тем не менее, Вы не признаете такое доказательства. Второй вопрос: какие способы доказательства Вы признаете? Можно ограничиться только утверждениями вида $\forall \alpha \exists \beta \forall i (\dots)$.

Как модератор, прошу Вас ответить на эти вопросы, иначе тема будет перенесена в Пургаторий как бессодержательная.

В рассматриваемом доказательстве теоремы Кантора о несчетности (что есть компиляция того, что имеется в трудах Г. Кантора, в самих трудах нечто иное, но не об этом речь) применяется "диагональный метод" в контексте доказательства от противного. То есть детально: рассматривается прямое составное утверждение - "множество М несчетно" (которое назовем утверждение F) и согласованное с F утверждение "возможно определить какой-то элемент $\beta$ из этого множества так, что он не получит номера ни в одной из попыток пронумеровать все элементы множества М" (которое назовем утверждение G). Чтобы высказывание "F и G" было ложным достаточно ошибочности одной из частей F или G (отрицанием прямого высказывания есть - $\neg F$ или $\neg G$). Далее допускается, что множество М - счетно, то есть для части F $\neg F$ предполагается верным и перестает, так сказать, играть логическую роль, и рассматривается только часть G. То есть далее рассматривается любая нумерация элементов М с попыткой показать, что элемент $\beta$ не имеет в ней своего номера, но не потому, что такого номера не существует, а потому, что мы не в состоянии проверить несуществование $\beta$ в последовательности $\alpha$, так как просто не в состоянии просмотреть все элементы бесконечного множества, при этом сказать что-то определенное о том какое $\beta$ конкретно заранее мы также не можем, так как $\beta$ определяется при нашей непосредственной проверке.
PS Наверно можно в данном случае говорить о логической ошибке, так как "не смогли
найти" не эквивалентно "не существует". Нельзя в процессе логического вывода вдруг
заменять одну логику другой.

[Someone]

Извините, Мастак, но Вы так и не ответили на совершенно конкретные вопросы, сформулированные в сообщении модератора. Или философы принципиально не могут отвечать на конкретные вопросы, требующие столь же конкретных ответов?

[Karan]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Пургаторий (М)»
Причина переноса: отказ топикстартера четко сформулировать теорию, в рамках которой ведется доказательство.

[Someone]

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

Из "Н. К. Верещагин, А. Шень Начала теории множеств"

В "доказательстве" составляется последовательность $\beta$ так, чтобы $ \beta_k, где k=0..i, $ на $i$-ом шаге выборки-рассмотрения не встречались в верхней части таблицы, НО это вовсе не означает, что вся последовательности $\beta$ не существует в нижней, по предположению тоже пронумерованной части, которую еще только не успели рассмотреть, задавая (непредикативно) объект поиска в процессе поиска через: $\beta_j = 1 - \alpha_{jj}$ на $j$-том шаге поиска-рассмотрения, так как дойти до этого шага может быть не получится из-за того, что рассматриваемые последовательности из 0 и 1 БЕСКОНЕЧНЫ же. А если не получится, то, значит, и конструктивно доказать таким способом невозможно.

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

О непредикативности. Вы явно не понимаете, что такое непредикативное определение. Посмотрим математическую энциклопедию.
Математическая энциклопедия, том 3. "Советская энциклопедия", Москва, 1982.

Цитата:

НЕПРЕДИКАТИВНОЕ ОПРЕДЕЛЕНИЕ — определение, осмысленность к-рого предполагает наличие определяемого объекта.
… Если фиксирован язык, на к-ром выражаются свойства, то понятие непредикативности уточняется следующим образом. Свойство (точнее, языковое выражение, выражающее это свойство) наз. непредикативным, если оно содержит связанную переменную, в область изменения к-рой попадает определяемый объект.

Например, "наименьшее положительное число" — это число $u$, определяемое свойством $u>0\wedge\forall x(x>0\Rightarrow u\leqslant x)$. Здесь есть связанная переменная $x$, которая пробегает множество положительных чисел. Поскольку определяемое число $u$ принадлежит множеству положительных чисел, то определение непредикативно. В данном случае такое число $u$ не существует. В других случаях непредикативно определяемый объект может благополучно существовать. Например, "точная верхняя грань подмножества множества действительных чисел" существует (обычно это определение допускает для точной верхней грани также значения $+\infty$ и $-\infty$, то есть, формулируется для расширенной числовой прямой).

В случае диагонального метода последовательность $\beta$ определяется формулой $\forall i(i\in\mathbb N\Rightarrow\beta_i=1-\alpha_{ii})$. Здесь есть только одна связанная переменная — $i$, которая пробегает множество натуральных чисел, и определяемая последовательность $\beta$ ни в коем случае не попадает в множество возможных значений переменной $i$, так как является не натуральным числом, а (бесконечной) последовательностью нулей и единиц. Поэтому данное определение предикативно.

Претензии к данному определению вообще выглядят как дурной анекдот. Например, мы можем рассмотреть функцию двух переменных $f(x,y)$, где $x$ и $y$ — любые действительные числа (то есть, определённую на $\mathbb R^2$), принимающую действительные значения, и определить "диагональную" функцию одной переменной по формуле $g(x)=1-f(x,x)$, или, в более формальной формулировке, $\forall x(x\in\mathbb R\Rightarrow g(x)=1-f(x,x))$. Против такого определения тоже есть возражения? Ну так $\beta$ и $\alpha$ отличаются от $g$ и $f$ только областью определения.

Как видим, непредикативность не имеет никакого отношения ни к бесконечности, ни к мифическим "процессам поиска". Нет также никакого "достраивания" и "откусывания" бесконечности.

О конструктивности. В классической математике ни о какой конструктивности речи не идёт. Уже рассуждение "возьмём любое число $x$ из интервала $(a,b)$", не сопровождаемое указанием конкретного числа (например, $x=\frac 12(a+b)$), является неконструктивным. В более сложных случаях указание конкретного объекта может оказаться невозможным, несмотря на то, что его существование доказано. Поэтому, например, критика аксиомы выбора "за неконструктивность" вызывает у меня недоумение: аксиома выбора имеет ровно такую же степень неконструктивности, как и приведённое выше рассуждение с выбором произвольного числа, где аксиома выбора не применяется. И в доказательстве теоремы Кантора аксиома выбора никаким способом не употребляется.

Однако в математике существует целый ряд конструктивистских направлений, отличающихся друг от друга пониманием конструктивности. С интуиционистским направлением я не знаком, но с советской школой конструктивизма знакомился: внимательно прочёл учебник (Б. А. Кушнер. Лекции по конструктивному математическому анализу. "Наука", Москва, 1973) и несколько статей в математических журналах. Здесь всё основано на алгорифмах (это одна из формализаций понятия "алгоритм", но представители этого направления пишут "ф" вместо "т"). Определено понятие записи алгорифма, то есть, представления его конечной строкой символов, которую могут обрабатывать другие алгорифмы. Разработаны методы, позволяющие использовать уже построенные алгорифмы в качестве составных частей других алгорифмов. Доказано существование универсального алгорифма, который, получив на входе запись какого-нибудь алгорифма и исходные данные для него, может смоделировать его работу и получить на выходе результат (или не получить, если моделируемый алгорифм не останавливается).

С точки зрения конструктивного математического анализа (конструктивная — это уточнение далее подразумевается) последовательность $\gamma$ нулей и единиц есть алгорифм, который, получив на входе натуральное число $i$, обязательно останавливается и на выходе даёт число $\gamma_i$, равное $0$ или $1$. Соответственно, последовательность последовательностей нулей и единиц есть алгорифм $\alpha$, который, получив на входе натуральное число $i$, обязательно останавливается и выдаёт на выходе запись алгорифма $\alpha_i$, который является последовательностью нулей и единиц. В свою очередь, алгорифм $\alpha_i$, получив на входе натуральное число $j$, обязательно останавливается и выдаёт на выходе ноль или единицу (полученный результат обозначим $\alpha_{ij}$. Пользуясь стандартными конструкциями, можно построить алгорифм $\beta$, который, получив на входе запись алгорифма $\alpha$ и натуральное число $i$, обязательно останавливается и выдаёт $\beta_i=1-\alpha_{ii}$. Заметим, что, имея в своём распоряжении универсальный алгорифм, мы можем работать исключительно с записями алгорифмов. Таким образом, диагональная конструкция Кантора полностью реализуется конструктивными методами. Доказываемое при этом утверждение формулируется так: множество конструктивных последовательностей нулей и единиц эффективно несчётно. Заметим, что аналог теоремы Кантора о несчётности множества действительных чисел в конструктивном анализе формулируется так: множество конструктивных действительных чисел эффективно несчётно. Эффективная несчётность несколько сильнее неперечислимости: из эффективной несчётности неперечислимость следует, а обратное — нет.

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

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

применяется "диагональный метод" в контексте доказательства от противного

Может быть, кому-то это покажется удивительным, но я никогда не видел доказательства теоремы Кантора, использующего метод "от противного". В сборнике трудов Кантора я нашёл два доказательства теоремы о несчётности множества действительных чисел (без использования диагонального метода) и одно доказательство несчётности множества двоичных последовательностей (диагональным методом). Ни одно из них не использует метода "от противного". Два из них полностью процитированы в сообщении http://dxdy.ru/post414177.html#p414177. Доказательство теоремы о несчётности множества действительных чисел диагональным методом можно найти в книге Клини. Оно тоже не использует метода "от противного" и процитировано в упомянутом выше сообщении. Там же есть ссылки на сборник трудов Кантора и на книгу Клини.

Внимательно присмотревшись к доказательству из книги Верещагина и Шеня, на которую ссылается Мастак, можно обнаружить, что оно тоже не использует метода "от противного", несмотря на то, что в начале доказательства делается предположение "Предположим, что оно счётно. Тогда все последовательности нулей и единиц можно перенумеровать", а завершается доказательство фразой "А мы предположили, что таблица включает в себя все последовательности — противоречие". Дело в том, что ни построение последовательности $\beta$, ни доказательство того, что $\forall i(i\in\mathbb N\Rightarrow\beta\neq\alpha_i)$ никаким способом не использует сделанное предположение. Выбросьте это предположение и последнюю фразу, и у Вас останется вполне корректное доказательство. Наоборот: возьмите доказательство любой теоремы, не использующее метода "от противного", в начале доказательства сделайте предположение, противоречащее утверждению теоремы, а в конце добавьте, что получилось противоречие. Формально получается доказательство "от противного". Но стоит ли заниматься такими упражнениями?
Собственно, я не понимаю, откуда взялись такие доказательства "от псевдопротивного".