Диагональный метод Кантора, помогите понять мою ошибку

[Redkhmer]

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

[Brukvalub]

Redkhmer в сообщении #1005754 писал(а):

..выходит что в результате попытки биекции мы получили только одну единственную последовательность в нее не вошедшую..

Это ложное утверждение. Правильное утверждение: получена, как минимум, одна "лишняя" последовательность.

[ИСН]

Redkhmer в сообщении #1005754 писал(а):

то есть: выходит что в результате попытки биекции мы получили только одну единственную последовательность в нее не вошедшую

По крайней мере одну. Да. Этого достаточно. Мы ведь перед этим что предполагали? э?

[Anton_Peplov]

Redkhmer в сообщении #1005754 писал(а):

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

Нет, нельзя. "По крайней мере один" не то же, что "ровно один".
Теорема. На Земле есть по крайней мере один человек.
Доказательство. Я - человек, и я на Земле.
Теорема доказана.

Вопрос к топикстартеру: следует ли из этого, что на Земле ровно один человек - я?

Доказательство методом Кантора показывает, что для каждой счетной системы подмножеств $\mathbb{N}$ найдется хотя бы одно подмножество $\mathbb{N}$, не входящее в эту систему, но не показывает, сколько подмножеств $\mathbb{N}$ в нее не входит. То, что их континуум - это более сильная теорема.

(Оффтоп)

Уважаемый Redkhmer, старайтесь излагать свои мысли яснее.

[AGu]

(Занудство)

Anton_Peplov, конечно, говорит дельные вещи. Но ваш покорный, страдающий недержанием занудства, вынужден слегка уточнить один незначительный моментик.

Anton_Peplov в сообщении #1005767 писал(а):

То, что их континуум - это более сильная теорема.

В некотором смысле это «более слабая теорема», так как она тупо повторяет определение континуума или просто недалеко от него убежала. Иногда континуум определяют именно как мощность $\mathcal P(\mathbb N)$. (Чаще, конечно, как мощность $\mathbb R$, но равномощность $\mathbb R$ и $\mathcal P(\mathbb N)$ — невелика теорема.)

[Redkhmer]

Спасибо за ответы, я искал свою ошибку и теперь область поиска сузилась, но все равно точка ошибки пока не точка, а окрестность.

Anton_Peplov писал(а):

Вопрос к топикстартеру: следует ли из этого, что на Земле ровно один человек - я?

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

[AGu]

Redkhmer в сообщении #1005855 писал(а):

нужно описать некий вечно работающий генератор

Если угодно, у Вас уже есть этот генератор. Разобравшись с диагональным доказательством Кантора, Вы научились для любого счетного подмножетва $X\subset\{0,1\}^{\mathbb N}$ определять элемент $f(X)\in\{0,1\}^{\mathbb N}$, не принадлежащий $X$. Как легко видеть, если к счетному множеству добавить один элемент, то снова получится счетное множество. Теперь запускаем генератор

$X_1:=X\cup\{f(X)\},\ X_2:=X_1\cup\{f(X_1)\},\ \dots,\ X_{n+1}:=X_n\cup\{f(X_n)\},\ \dots$

и наблюдаем, как вне $X$ постепенно появляется бесконечное множество $\{f(X),f(X_1),f(X_2),\dots\}$. Это, конечно, не дает понять, что дополнение $X$ превосходит $X$ по мощности, но то, что это дополнение бесконечно, видно сразу.

[Redkhmer]

Так вот как же дальше, понять что дополнение превосходит по мощности изначальное множество?

[AGu]

Redkhmer в сообщении #1005865 писал(а):

Так вот как же дальше, понять что дополнение превосходит по мощности изначальное множество?

Насколько я понял, Вы владеете доказательством «от противного». Вы его поняли? Если так, то Вы поняли, почему это дополнение несчетно. А «увидеть» этот факт как-то «конструктивно» Вам не удастся при всем желании: конструктивные построения (в традиционном смысле) дальше счетных множеств не достреливают.

[Redkhmer]

Тупик интуиционизма

[grizzly]

Redkhmer
Возможно, Вашей интуиции нужен какой-то толчок, чтобы сбить её ошибочные настройки. Я могу посоветовать посмотреть, как сработает подобный "диагональный" метод в конечном случае.

Возьмите 5 любых двоичных последовательностей длины 5; выпишите их одна под другой; докажите таким же диагональным методом (от противного), что это не все двоичные последовательности длины 5. Теперь Вы можете наглядно видеть, как здесь сработало доказательство от противного и понять, что Вы нашли только одну из 27 отсутствующих последовательностей, но этого достаточно для доказательства от противного. Теперь попытайтесь в уме увеличивать длину последовательностей (брать 6 по 6, 7 по 7 и т.д.). Тогда Вы заметите, насколько быстро растёт отсутствующий остаток. (Этот пример ничего не доказывает в Вашем вопросе, но может помочь переключить интуицию.)

[Redkhmer]

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

-- 20.04.2015, 15:55 --

grizzly
Этот пример говорит факт очевидный до построений 2 в степени n (количество двоичных последовательностей) минус n - стремится к бесконечности, скорее всего этого факта достаточно. Еще посоветовали объяснение "На самом-то деле это очевидный факт: если хотя бы одно из множеств A и B бесконечное, то мощность их объединения - это максимальная из мощностей A и B. Таким образом, если A - счётное, а объединение A и B континуум, то B - континуум. " сейчас по книге Верещагина Шеня ищу понятное мне объяснение этой теоремы. На самом деле в своих медитациях над этим вопросом я пытаюсь провести внутренний тест на интуционизм, контсруктивизм, логицизм или формализм или даже математический платонизм является моим самым внутренним отношением к математике? Насколько вообще корректен такой вопрос? Ведь естествено предположить что эти отношения вибрируют переходя в друг друга и никакое нельзя считать основным. Быть может надо было тему формулировать изначально в таком направлении. И вообще подобные вопросы насколько и где реллевантны?

[AGu]

Увы, тут я не спец. Я на самом деле имел в виду несколько иное. Например, Гёдель, вводя понятие конструктивного множества, грубо говоря, считал допустимым взятие объединения по любому — в том числе, несчетному — ординалу. Есть разные подходы к понятию конструктивности, и некоторые из них «достреливают» куда угодно. Но это не означает, что они отвечают конструктивной интуиции.

[Xaositect]

В конструктивизме и прочем интуиционизме все то же самое. Нельзя построить сюръекцию $\mathbb{N}\to 2^{\mathbb{N}}$, значит $2^{\mathbb{N}}$ больше, чем $\mathbb{N}$. (Естественно, $2^{\mathbb{N}}$ в конструктивизме это только вычислимые функции $\mathbb{N}\to \mathbf{2}$, но на диагональной конструкии это не отражается).

[iifat]

Как-то, имхо, не на то вы все обращаете внимание. Таки ж да, доказательство методом Кантора доказывает существование одного элемента, но это неважно, будь он и правда один-одинёшенек. Упор — на начале: предположим, мы как-то смогли перенумеровать все элементы. И тут ехидный Кантор предъявляет нам ещё один! И один, два, десять — неважно, именно потому что мы, в гордыне своей, обещали ему, что перенумеровали всё!
Дальше, более другими методами, можно показать, что на самом-то деле в стороне остался не один, не два, и даже не бесконечное множество, равномощное натуральному ряду — но это, повторюсь, следующие вопросы, ответы на которые, разумеется, интересны, но утверждения теоремы они уже не меняют.