Теорема о неравномощности множеств

[gogoshik]

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

Вслед за mihaild, категорически рекомендую не делать такого предположения и вообще не использовать метод "от противного". Это только заморачивает мозги. Прямо доказываем, что произвольно взятое отображение $f\colon A\to 2^A$ не является сюръекцией.

mihaild в сообщении #1212331 писал(а):

Можно так: возьмем какое-нибудь отображение $f : A \to 2^A$. По нему строится $B_f = \{x | x \in A, x \notin f(x)\}$. Методом пристального взгляда доказываем, что ни для какого $y \in A$ не получится $f(y) = B$. Значит, $B$ не лежит в образе $f$, и, следовательно, $f$ - не биекция.
Т.к. $f$ было произвольным отображением, то биекций (и даже сюръекций) $A \to 2^A$ не бывает.

Хотел бы разобраться в этой идее подробнее. Есть ли книга или статья где рассматривается такой вариант доказательства теоремы? Предложение - "Методом пристального взгляда доказываем, что ни для какого $y \in A$ не получится $f(y) = B$" - не убедительно. Тут я хотел бы увидеть детали.

И объясните плиз, почему мы это вдруг пользуемся построением нового множества $B$ и почему пользуемся аксиомой выделения, ведь есть другие аксиомы теории множеств? Это какой то ключевой секрет?

[mihaild]

gogoshik в сообщении #1212542 писал(а):

Методом пристального взгляда доказываем, что ни для какого $y \in A$ не получится $f(y) = B$

Odysseus в сообщении #1212346 писал(а):

Ну или посмотрите пристально на предложения 3-5 из ссылки на доказательство
, которое вы привели ранее

Вообще ничего принципиально не поменялось. Единственное изменение - вместо предположения о существовании прообраза у любого элемента мы опровергли более слабое предположение о существовании прообраза у $B$ (а опровержение более слабого предположения опровергает и более сильное).

gogoshik в сообщении #1212542 писал(а):

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

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

[gogoshik]

Спасибо :)

mihaild в сообщении #1212543 писал(а):

Потому что здесь нужна она - других способов построить подмножество произвольного множества нет.

Но вот нам в теореме даны два множества: $A$ и $2^A$. Из двух может быть и можно построить подмножество?

mihaild в сообщении #1212543 писал(а):

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

Я не знаю ответ на этот вопрос. Можно еще спросить почему отвертка лучше чем шуроповерт. Инструменты разные бывают. Кому что нравится.

[Someone]

gogoshik в сообщении #1212571 писал(а):

Я не знаю ответ на этот вопрос.

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

gogoshik в сообщении #1212542 писал(а):

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

Есть.

П. Дж. Коэн. Теория множеств и континуум-гипотеза. "Мир", Москва, 1969.
Глава II, § 4.

К. Куратовский, А. Мостовский. Теория множеств. "Мир", Москва, 1970.
Глава V, § 4, § 5.

[gogoshik]

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

Кстати, Вы-то аксиомы ZFC знаете?

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

Спасибо за книги! Скажите, а эти учебники актуальны, сейчас тоже по ним учат аксиоматическую теорию множеств?

[Someone]

gogoshik в сообщении #1212613 писал(а):

Я про аксиомы читал, когда увидел в доказательстве теоремы Кантора ссылку на аксиому выбора.

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

gogoshik в сообщении #1212613 писал(а):

Вы можете меня научить пользоваться этими аксиомами, плиз?

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

gogoshik в сообщении #1212613 писал(а):

Скажите, а эти учебники актуальны, сейчас тоже по ним учат аксиоматическую теорию множеств?

Книга П. Дж. Коэна — вообще не учебник, а монография, в которой излагается метод вынуждения (форсинга) и его применения для решения ряда проблем теории множеств. Вы пока в эти дебри не лезьте, посмотрите только, как там доказывается теорема Кантора. Ну и ознакомьтесь с начальными главами, если Вы имеете в виду изучение теории множеств на не совсем элементарном уровне.
Я про неё вспомнил потому, что в ней доказательство теоремы Кантора, на мой взгляд, именно такое, каким оно должно быть.

Книга К. Куратовского и А. Мостовского является весьма серьёзным учебником. Принятая там аксиоматика имеет пару особенностей.
1) Авторы почему-то не включили в список аксиому регулярности (фундирования), хотя сами же пишут, что, по их мнению, эта аксиома очевидно истинна. Почему они так сделали, я не знаю. В их книге это ни к каким видимым проблемам не привело.
2) Авторы придумали собственную аксиому реляционных типов, которая, насколько я помню, употребляется у них один раз для того, чтобы сказать, что мощность множества — это реляционный тип чего-то там (в книге написано, чего именно).

[Anton_Peplov]

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

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

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

[atlakatl]

Odysseus в сообщении #1212366 писал(а):

$2^A$ это просто обозначение, которое соответствует реальной степени лишь для конечных множеств

Это не просто обозначение. Для конечных множеств оно абсолютно точное. А вот для бесконечных именно степень двойки позволяет поймать следующее (строго следующее) кардинальное число. - При условии верности континуум-гипотезы, конечно. Доказать её - строго доказано - нельзя. Аксиомой её объявить почему-то не решаются. Видимо, её отрицание тоже сулит забавные результаты.

[Odysseus]

atlakatl в сообщении #1212656 писал(а):

Odysseus в сообщении #1212366 писал(а):

$2^A$ это просто обозначение, которое соответствует реальной степени лишь для конечных множеств

Это не просто обозначение. Для конечных множеств оно абсолютно точное.

Про конечные множества я же уже и написал выше.

atlakatl в сообщении #1212656 писал(а):

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

А это мне не очень понятно. Что значит, что это не просто обозначение для бесконечных множеств, и как именно степень двойки для них помогает что-то поймать?

[atlakatl]

Odysseus в сообщении #1212658 писал(а):

Что значит, что это не просто обозначение для бесконечных множеств, и как именно степень двойки для них помогает что-то поймать?

Забываем про конечные множества и переходим к бесконечным.
Мощность множества натуральных чисел ${\displaystyle {\mathbb {N} }} $ обозначается ${\displaystyle \aleph _{0}}$ («алеф-нуль»). Это наименьшее кардинальное число. - Доказано.
Доказано также, что $2^{\aleph_0}=c$, где $c$ мощность континуума, - мощность множества всех точек любого отрезка ненулевой длины.
А вот дальше сплошные загадки.
Есть ли между ${\displaystyle \aleph _{0}}$ и $c$ промежуточное по мощности кардинальное число?
Следующее кардинальное число получаются тем же возведением двойки в степень предыдущего кардинального числа.
Но можно ли вклинить в ряд кардинальных чисел ${\displaystyle \aleph _{1},\aleph _{2},\dots \aleph _{\omega },\aleph _{\omega +1},\dots \aleph _{\omega _{1}},\dots }$, зависит, видимо, от принимаемой системы аксиом. В рамках аксиоматики Цермело — Френкеля - доказано - опровергнуть или доказать это предположение нельзя.
Вот и считается, что именно степень двойки формирует строго следующее кардинальное число. - Я назвал результат этого метода "поймать".

[Odysseus]

atlakatl в сообщении #1212660 писал(а):

Мощность множества натуральных чисел ${\displaystyle {\mathbb {N} }} $ обозначается ${\displaystyle \aleph _{0}}$ («алеф-нуль»). Это наименьшее кардинальное число. - Доказано.

Это неверно. ${\displaystyle \aleph _{0}}$ это наименьшее бесконечное кардинальное число, а наименьшее кардинальное число это $0$, мощность пустого множества.

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

[atlakatl]

Odysseus в сообщении #1212661 писал(а):

Это неверно

Я ж сказал ранее:

atlakatl в сообщении #1212660 писал(а):

Забываем про конечные множества и переходим к бесконечным.

Мостиком между конечным множеством и натуральным рядом является феномен "предел". Т.е. непреодолимой границы между ними нет. И теория пределов - в данном случае предел стремится к бесконечности - работает.
Почему следующее кардинальное число нельзя получить, скажем, $ {\displaystyle \aleph _{n}} = ({\displaystyle \aleph _{n-1}})^2 $ - не знаю. Будем ждать веского слова ЗУ. Которые сейчас придут и всех разгонят по палатам.

[Mikhail_K]

atlakatl в сообщении #1212660 писал(а):

Вот и считается, что именно степень двойки формирует строго следующее кардинальное число.

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

atlakatl в сообщении #1212665 писал(а):

Мостиком между конечным множеством и натуральным рядом является феномен "предел". Т.е. непреодолимой границы между ними нет. И теория пределов - в данном случае предел стремится к бесконечности - работает.

Это что-то невнятное.

atlakatl в сообщении #1212665 писал(а):

Почему следующее кардинальное число нельзя получить, скажем, $ {\displaystyle \aleph _{n}} = ({\displaystyle \aleph _{n-1}})^2 $ - не знаю.

Потому что "квадрат" любого бесконечного кардинального числа равен ему самому.

GAA:

Отступление на тему правил форума выделено в самостоятельную ветку.

[Odysseus]

atlakatl в сообщении #1212665 писал(а):

Odysseus
Мостиком между конечным множеством и натуральным рядом является феномен "предел". Т.е. непреодолимой границы между ними нет. И теория пределов - в данном случае предел стремится к бесконечности - работает.

Я не понимаю что эти слова значат...

atlakatl в сообщении #1212665 писал(а):

Почему следующее кардинальное число нельзя получить, скажем, $ {\displaystyle \aleph _{n}} = ({\displaystyle \aleph _{n-1}})^2 $ - не знаю. Будем ждать веского слова ЗУ. Которые сейчас придут и всех разгонят по палатам.

Потому, что $ \displaystyle \aleph _{n-1}^2 $ обозначает кардинальное число декартова произведения множеств с кардинальным числом $ \displaystyle \aleph _{n-1} $, и поэтому $ ({\displaystyle \aleph _{n-1}})^2 = {\displaystyle \aleph _{n-1}} $ для бесконечных кардиналов. Вспомните, например, что квадрат равномощен отрезку и почитайте про арифметику кардинальных чисел.

[Someone]

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

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

Наличие аксиомы регулярности позволяет проводить доказательства по индукции такого рода: если 1) пустое множество обладает свойством $P$ и 2) из того, что все элементы некоторого множества $M$ обладают свойством $P$, следует, что и само множество $M$ обладает свойством $P$, то все множества обладают свойством $P$.

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

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

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

Ну, например, сформулированный выше метод индукции не доказывается. Удаление аксиомы из непротиворечивой системы не может привести к противоречию. И да, аксиома регулярности — это дополнительное средство доказательства, которое иной раз позволяет упростить доказательство.

Odysseus в сообщении #1212366 писал(а):

$2^A$ это просто обозначение, которое соответствует реальной степени лишь для конечных множеств

Самая настоящая степень при любой мощности. Особенно если вспомнить, что в теории множеств число $2$ — это множество, состоящее из двух элементов: $2=\{0,1\}$.

Odysseus в сообщении #1212366 писал(а):

если $a$ это число элементов в конечном множестве $A$, то в множестве всех его подмножеств, обозначаемом $2^A$, будет $2^a$ элементов

И для бесконечных множеств точно так же. Только термин "число элементов" в этом случае обычно не употребляют.

atlakatl в сообщении #1212656 писал(а):

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

atlakatl в сообщении #1212656 писал(а):

- При условии верности континуум-гипотезы, конечно.

Бред. Континуум-гипотеза касается только равенства $2^{\aleph_0}=\aleph_1$, на другие кардиналы она не распространяется. А [GCH] — слишком сильная гипотеза, в неё никто не верит.

atlakatl в сообщении #1212656 писал(а):

Аксиомой её объявить почему-то не решаются. Видимо, её отрицание тоже сулит забавные результаты.

Видите ли, если кому-то для доказательства теоремы понадобилась истинность континуум гипотезы, он так и пишет:
Теорема ([CH]). …
А если понадобилось отрицание континуум-гипотезы, то он пишет
Теорема ([¬CH]). …
Так же он поступает, если ему нужны какие-то другие предположения, не следующие из аксиом.

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

atlakatl в сообщении #1212660 писал(а):

Мощность множества натуральных чисел ${\displaystyle {\mathbb {N} }} $ обозначается ${\displaystyle \aleph _{0}}$ («алеф-нуль»). Это наименьшее кардинальное число.

Наименьшее бесконечное кардинальное число.

atlakatl в сообщении #1212660 писал(а):

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

Это ерунда. Если бы была справедлива обобщённая континуум-гипотеза, то это было бы так, но …

atlakatl в сообщении #1212660 писал(а):

Вот и считается, что именно степень двойки формирует строго следующее кардинальное число.

А чего это Вы о себе во множественном числе говорите? Никто другой так не считает. И не надо тут всякие выдумки излагать под видом теории множеств.

atlakatl и Odysseus, перестали бы Вы тут всякую ерунду городить. Возьмите лучше учебник по теории множеств и изучайте его.