2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Диагональный метод Кантора, помогите понять мою ошибку
Сообщение20.04.2015, 00:32 
Аватара пользователя
Redkhmer в сообщении #1005754 писал(а):
..выходит что в результате попытки биекции мы получили только одну единственную последовательность в нее не вошедшую..
Это ложное утверждение. Правильное утверждение: получена, как минимум, одна "лишняя" последовательность.

 
 
 
 Re: Диагональный метод Кантора, помогите понять мою ошибку
Сообщение20.04.2015, 00:58 
Аватара пользователя
Redkhmer в сообщении #1005754 писал(а):
то есть: выходит что в результате попытки биекции мы получили только одну единственную последовательность в нее не вошедшую

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

 
 
 
 Re: Диагональный метод Кантора, помогите понять мою ошибку
Сообщение20.04.2015, 01:20 
Аватара пользователя
Redkhmer в сообщении #1005754 писал(а):
можно ли утверждать что "разность" множеств натурального ряда и бесконечных нулей и единиц равномощна множеству из одного элемента.

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

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

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

(Оффтоп)

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

 
 
 
 Re: Диагональный метод Кантора, помогите понять мою ошибку
Сообщение20.04.2015, 10:27 

(Занудство)

Anton_Peplov, конечно, говорит дельные вещи. Но ваш покорный, страдающий недержанием занудства, вынужден слегка уточнить один незначительный моментик.
Anton_Peplov в сообщении #1005767 писал(а):
То, что их континуум - это более сильная теорема.
В некотором смысле это «более слабая теорема», так как она тупо повторяет определение континуума или просто недалеко от него убежала. Иногда континуум определяют именно как мощность $\mathcal P(\mathbb N)$. (Чаще, конечно, как мощность $\mathbb R$, но равномощность $\mathbb R$ и $\mathcal P(\mathbb N)$ — невелика теорема.)

 
 
 
 Re: Диагональный метод Кантора, помогите понять мою ошибку
Сообщение20.04.2015, 14:41 
Спасибо за ответы, я искал свою ошибку и теперь область поиска сузилась, но все равно точка ошибки пока не точка, а окрестность.
Anton_Peplov писал(а):
Вопрос к топикстартеру: следует ли из этого, что на Земле ровно один человек - я?

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

 
 
 
 Re: Диагональный метод Кантора, помогите понять мою ошибку
Сообщение20.04.2015, 14:54 
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$ по мощности, но то, что это дополнение бесконечно, видно сразу.

 
 
 
 Re: Диагональный метод Кантора, помогите понять мою ошибку
Сообщение20.04.2015, 15:01 
Так вот как же дальше, понять что дополнение превосходит по мощности изначальное множество?

 
 
 
 Re: Диагональный метод Кантора, помогите понять мою ошибку
Сообщение20.04.2015, 15:06 
Redkhmer в сообщении #1005865 писал(а):
Так вот как же дальше, понять что дополнение превосходит по мощности изначальное множество?
Насколько я понял, Вы владеете доказательством «от противного». Вы его поняли? Если так, то Вы поняли, почему это дополнение несчетно. А «увидеть» этот факт как-то «конструктивно» Вам не удастся при всем желании: конструктивные построения (в традиционном смысле) дальше счетных множеств не достреливают.

 
 
 
 Re: Диагональный метод Кантора, помогите понять мою ошибку
Сообщение20.04.2015, 15:12 
Тупик интуиционизма

 
 
 
 Re: Диагональный метод Кантора, помогите понять мою ошибку
Сообщение20.04.2015, 15:20 
Аватара пользователя
Redkhmer
Возможно, Вашей интуиции нужен какой-то толчок, чтобы сбить её ошибочные настройки. Я могу посоветовать посмотреть, как сработает подобный "диагональный" метод в конечном случае.

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

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

-- 20.04.2015, 15:55 --

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

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

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

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

 
 
 [ Сообщений: 53 ]  На страницу 1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group