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

[Anton_Peplov]

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

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

Удаление аксиомы из непротиворечивой системы не может привести к противоречию.

нужен некоторый опыт работы с формальными системами, какового опыта у читателя может и не быть.

[Odysseus]

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

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

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

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

Я отвечал этим на конкретный комментарий

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

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

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

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

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

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

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

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

Вот именно потому и не так, что это не "число элементов". Еще раз посмотрите на что я отвечал.

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

[g______d]

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

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

Ну если уж совсем честно, то $2^2$ и $4$ -- это разные множества (если определять $0=\varnothing$ и $n+1=n\cup\{n\}$ для $n\geqslant 1$.

[Someone]

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

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

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

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

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

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

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

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

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

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

Тем не менее, и для бесконечных кардиналов речь идёт о настоящих произведениях и настоящих степенях — точно так же, как для конечных. Это не просто слова.

В теории множеств есть такая конструкция — произведение индексированного семейства множеств. Она одинаковая и в конечном, и бесконечном случае. Произведение кардиналов — это мощность произведения множеств соответствующей мощности. Если множества одинаковые, получается степень.

Выглядит это так. Пусть $T$ — множество индексов, и каждому $t\in T$ поставлено в соответствие множество $X_t$. Тогда произведение $\prod\limits_{t\in T}X_t$ определяется как множество таких отображений $f\colon T\to\bigcup\limits_{t\in T}X_t$, что $f(t)\in X_t$ для всякого $t\in T$. Это определение одинаково работает и для конечного $T$, и для бесконечного. И

$$\prod\limits_{t\in T}\lvert X_t\rvert=\left\lvert\prod\limits_{t\in T}X_t\right\rvert.$$

В случае конечных $T$ и $X_t$ это теорема комбинаторики, а в общем случае — определение.
Если же $X_t=X$ для всех $t\in T$, то пишут проще:

$$\lvert X\rvert^{\lvert T\rvert}=\left\lvert X^T\right\rvert.$$

Вот и появляются произведения и степени. В бесконечном случае такие же настоящие, как в конечном.

А множество подмножеств множества $T$ легко отождествляется с $2^T$, где $2$ — множество из двух элементов.

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

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

Извините, если что не так сказал, у меня тоже бывают неточности в формулировках. Но я стараюсь, чтобы их не было.

g______d в сообщении #1212721 писал(а):

Ну если уж совсем честно, то $2^2$ и $4$ -- это разные множества (если определять $0=\varnothing$ и $n+1=n\cup\{n\}$ для $n\geqslant 1$.

Я, собственно, говорю о том, что число элементов произведения множеств $2\times 2$ равно произведению чисел $2\cdot 2$. Разумеется, множества разные, поскольку произведения определяются совсем по-разному.

[Odysseus]

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

В теории множеств есть такая конструкция — произведение индексированного семейства множеств. Она одинаковая и в конечном, и бесконечном случае. Произведение кардиналов — это мощность произведения множеств соответствующей мощности. Если множества одинаковые, получается степень.
[...]
Вот и появляются произведения и степени. В бесконечном случае такие же настоящие, как в конечном.

Я это все знаю, поэтому же, например, и писал уже ранее в этом треде:

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

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 в сообщении #1212728 писал(а):

А множество подмножеств множества $T$ легко отождествляется с $2^T$, где $2$ — множество из двух элементов.

Конечно, я же про это тоже уже писал:

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

...символ количества отображений из одного множества в другое (для булеана, очевидно, в множество из двух элементов).

Я не пытаюсь что-то доказать, просто хотелось бы, чтобы меня понимали.

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

Извините, если что не так сказал, у меня тоже бывают неточности в формулировках. Но я стараюсь, чтобы их не было.

Все ок, у меня некоторые формулировки в самом деле были неидеальны. Просто хотелось обратить внимание ТС, что это не "обычная простая арифметика", и интуиция только из последней может подводить.

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

[Odysseus]

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

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

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

Есть.

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

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

gogoshik, я тут подумал, что вам будет полезно разобраться в еще одном методе доказательства теоремы Кантора. В Коэне и Куратовском-Мостовском она, в общем-то, тоже доказывается в рамках тех же идей, что и доказательство на которое вы ссылались в самом начале (Теорема Кантора). Это наиболее короткий и популярный способ, но в силу некоей абстрактности в построении подмножества $B$ и "рефлексивных" рассуждений в стиле "брадобрей бреет всех, кто не бреется сам", он у некоторых в самом деле вызывает некое чувство дискомфорта и неуверенности.

Но есть еще один метод доказательства, который вы можете прочитать во "Введение в теорию множеств и общую топологию" П.С. Александрова (1977), глава 1, § 6, теоремы 15 и 16. Это более "прямой" способ, который вроде сам Кантор и использовал (при этом выстраиваемая структура и логика рассуждений практически идентичны диагональному методу Кантора доказательства неравномощности множеств натуральных и вещественных чисел). После этого постарайтесь для себя понять в чем эти два способа доказательства теоремы Кантора близки, и как первый способ можно немного переформулировать на языке близком ко второму способу.

(Оффтоп)

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

[gogoshik]

Спасибо! Обязательно посмотрю рекомендуемую литературу.

[shkolnik]

Про аксиому регулярности, вспомнилось, как в детстве читал связки журналов "Квант" на даче и запала одна статья. Речь шла о Библиотеке, в которой есть все книги. Сколько их может быть вообще, если в каждой книге не более чем столько-то страниц. Подробности не важны. Задело определение каталога всех каталогов, который соответственно, должен быть включен в самого себя (быть одной из книг библиотеки).
Впоследствии я встречал этот мотив в произведениях каких-то фантастов. Неважно. Смысл в том, что противоречия в существовании каталога всех каталогов (множества всех множеств) я тогда не нашел. Ничего противоестественного во включении множества в само себя в качестве элемента я не обнаружил.
Спустя время, я узнал о наивной теории множеств, и каким образом из предположения, о множестве всех множеств выводится противоречие. Это меня так потрясло, что я сразу отбросил свою детскую интуицию о том, что каталог всех каталогов существует.
Спустя время, я узнал об определении множеств и аксиоме регулярности. Понял в чем отличие множества от каталога. Вновь проснулась детская интуиция, которая сказала: "Я же говорила, что ничего противоречивого во включении каталога (множества) в самого себя нет".
Чуть позже я осознал, что проблема не в регулярности (включении множества в само себя), а в слове "всех" (в кванторе всеобщности для однотипных объектов).
И только потом ко мне пришло понимание, что аксиома регулярности "перпендикулярна остальным аксиомам теории множеств".
Это случилось, когда я специально стал пытаться построить нерегулярные множества и применять к ним аксиомы(схемы) выделения, индукции.
Например, зададим множества явно:
$a=\{b,c,d\}$
$b=\{a,c,d\}$
$c=\{a,b,d\}$
$d=\{\{a,b\},c\}$
Верно ли, что $a>b$ ? $d=c$ ? и т.д.
Прежде чем ответить на эти вопросы, я понял следующее.
Смысл в том, что все это никак не отражается на "универсуме", где приняты аксиомы ZF(С). Регулярность или не регулярность к этому совершенно перпендикулярна.
Приведу еще такой пример:
Попытайтесь явно выписать несколько первых множеств из $\omega$.
Примените к исходному множеству $\bigcup$ (т.е. возьмите множество, состоящее только из элементов, входящих в каждое множество исходного $\omega$. Теперь сравните, верно ли, что $\omega=\bigcup \omega$
Я это назвал (для себя) "элюминация", посмотрев, как это отражается на начальных элементах $\omega$.

Все дело в основании "множеств" и "свойств".
Вряд ли они совпадают.

[arseniiv]

shkolnik в сообщении #1213024 писал(а):

Смысл в том, что все это никак не отражается на "универсуме", где приняты аксиомы ZF(С).

Нет, на универсуме-то как раз отражается так же, как описали Anton_Peplov и Someone: в одном случае там такие множества есть, а в другом их нет. В одном случае будет, например, $x\in x\leftrightarrow x\ne x$, а в другом нет. Это вполне осязаемые отличия.

Притом некая «перпендикулярность», конечно, всё-таки есть, но опять же то, в чём она заключается, тут уже выше описали.

shkolnik в сообщении #1213024 писал(а):

"элюминация"

Ну хотя бы не иллюминация.

shkolnik в сообщении #1213024 писал(а):

Все дело в основании "множеств" и "свойств".
Вряд ли они совпадают.

Тут вы тоже открыли Америку. Коллекции множеств, определяемые свойствами (можно формально использовать записи вида $x\in\{a : \varphi\}$ как эквивалент $\varphi[x/a]$, и для оставшихся записей аналогично), называются классами, и, конечно, существуют классы, не являющиеся множествами — например, класс всех ординалов или как раз класс всех множеств. При этом о принадлежности (или непринадлежности) класса какому-то классу речи с самого начала не стоит.