Множество, большее многократного булеана счётного

[fractalon]

Можно ли теоретически доказать существование или несуществование такого множества, что оно в известном (строгом) смысле больше любого множества из последовательности ${\mathbb N}, 2^{\mathbb N}, 2^{2^{\mathbb N}}, 2^{2^{2^{\mathbb N}}}, \dots$? $2^A$ означает булеан множества $A$.

[mihaild]

Да, можно. Более обще - пусть у вас есть некоторое множество $A$. Как найти множество большей мощности, чем любой элемент $A$?
Для каждого отдельного элемента - взять его булеан, а для всех сразу?

[fractalon]

Булеан объединения? Да, точно. Спасибо!

[arseniiv]

В данном случае (множество $\{A, 2\uparrow A, 2\uparrow2\uparrow A, \ldots\}$*) брать булеан после объединения нет надобности — мощность его объединения будет больше мощности любого $2\uparrow\ldots\uparrow A$, ведь для каждого из них в этом объединении содержится и что-нибудь побольше.

Меня поначалу удивило, что это множество $\{A, 2\uparrow A, 2\uparrow2\uparrow A, \ldots\}$ вообще существует.

* $2\uparrow A\equiv 2^A$ и правоассоциативна — без стрелок неудобно.

[Mysterious Light]

arseniiv, а можете подробнее объяснить, почему класс $\{ (2\uparrow)^n A \;|\; n\in\mathbb{N} \}$ является множеством?

[arseniiv]

Посмотрите Куратовский, Мостовский, Теория множеств (я это там и вычитал). В переводе 1970 года, выпущенном в «Мире», это глава III §2 «Определения по индукции». Не буду говорить, что досконально проверил там одно тёмное место в таком «неограниченном» определении.

[Mikhail_K]

Mysterious Light в сообщении #1126663 писал(а):

а можете подробнее объяснить, почему класс $\{ (2\uparrow)^n A \;|\; n\in\mathbb{N} \}$ является множеством?

В ZFC есть такая "аксиома подстановки". Одна из её формулировок гласит:

Если $X$ - множество, $\varphi$ - такой двуместный предикат, что для каждого $x\in X$ найдётся не более одного $y$, удовлетворяющего $\varphi(x,y)$, то существует такое множество $Y$, что $y\in Y$ $\Leftrightarrow$ $\exists x\in X:$ $\varphi(x,y)$.

(см. Френкель, Бар-Хиллел. Основания теории множеств, глава 2, $\S$5.)

В этой формулировке объект $y$ не обязан быть членом какого-то заранее известного множества. Всё, что нужно от предиката $\varphi$ - это его верность или неверность для любого $x\in X$ и вообще любого объекта $y$, определённого средствами ZFC. В частности, брать булеаны от множеств ZFC позволяет.

Существует предикат $\varphi$ такой, что верны утверждения $\varphi(n,(2\uparrow)^nA)$ и только они. Если мы хотим абсолютной строгости, то это тоже надо как-то доказывать, но в принципе здесь это и так ясно. Ведь от предиката мы требуем только одного - верности или неверности для любых двух объектов.

Теперь достаточно применить аксиому подстановки к нашему $\varphi$ и $X=\mathbb{N}$.

[mihaild]

А так нельзя?
По индукции - $\forall n \in \mathbb{N} \exists! f: f-\text{функция на \{0,\ldots,n\}} \cap \forall m < n f(m + 1) = 2^{f(m)} \cap f(0) = A$ (тут надо много писать, но не видно, где могли бы возникнуть проблемы).
Тогда по аксиоме замены у нас есть функция из $\mathbb{N}$ в такие функции - возьмем их объединение и получим нужную функцию.

[arseniiv]

(Оффтоп)

Mikhail_K в сообщении #1126669 писал(а):

$\varphi$ - такой двуместный предикат

Ой. Я почему-то думал, что в аксиоме замены $\varphi$ должна соответствовать какая-то функция (в смысле множество — и тогда её сначала надо тоже построить). Да, так сомнения лично у меня развеиваются окончательно.

[alex_dorin]

в аксиоме подстановки нет никаких функций

[arseniiv]

(Оффтоп)

А у меня потому прошедшее время и употреблено.