Бесконечные кардинальные числа: n = n^2

[rishelie]

Профессор Снэйп в сообщении #309981 писал(а):

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

а нельзя проще? разность $\beta\setminus\alpha$ имеет порядковый тип, обозначим его $\gamma$.
ординал $\gamma$ имеет мощность $\beta$, т.к. в противном случае будет $\beta=|\alpha+_o\gamma|< \alpha+\beta=\beta$ для бесконечного $\alpha$ ($+_o$ - сумма ординалов). противоречие.
(все-таки теорема о сумме используется, и конструкции с чередованием чет-нечет не избежать)
а если мощность $\gamma$ равна $\beta$, то ординал $\gamma\ge\beta$ по определению кардинала.
это означает наличие естественной инъекции из $\beta$ в $\gamma$. обратная инъекция тривиальна.
далее теорема КБ.

[rishelie]

rishelie в сообщении #310019 писал(а):

но произвольный выбор все равно остается - это выбор $f:n\to X$. Однако, этот выбор однократный, и если он вмонтирован в определение $\Phi(x,y)$, то АС тут ни при чем.

но по-хорошему тут надо еще раскручивать все аккуратно. может быть, и упремся в дыру :)

нашел дыру, так что Вы правы :)
сначала я решил упростить подход: вместо сравнимости по мощности с кардиналами можно говорить о сравнимости с ординалами и рассматривать инъекции в $X$ с ординалов, тогда и рекурсия пойдет по классу ординалов.
но проблема в том, что когда строишь рекурсивное определение, нужно сначала задать не что иное, как функцию выбора :))
это функция должна работать так: F(Y)=y, где $Y\subseteq X$, $y\in X$.
Мы можем определить "хорошие" множества как те, для которых существует биекция с ординалом (кстати, класс таких множеств является моделью ZFC)
Так вот, чтобы построить нужную нам рекурсию, нужно уметь выбирать с помощью функции $F$ элемент вне хорошего множества. И вот это уже проблема.

[Профессор Снэйп]

rishelie в сообщении #310019 писал(а):

$\Phi(x,y)$, упомянутое выше, думаю, тут будет иметь очень громоздкий вид, т.к. оно будет включать процедуру построения $f_n$ через все $f_k$, $k<n$.

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

-- Пт апр 16, 2010 13:25:29 --

rishelie в сообщении #310053 писал(а):

а нельзя проще?

Ну, я бы не сказал, что это сильно проще

-- Пт апр 16, 2010 13:27:45 --

rishelie в сообщении #310167 писал(а):

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

Да, проблему Вы подметили верно: функция выбора, увы, нужна. Выбор тут у нас не однократный

[rishelie]

жаль.. все было так симпатично :))
может внести проект в ГД, чтобы узаконить АС? :)))

[Профессор Снэйп]

Надо ещё подумать. Или литературу почитать

-- Пт апр 16, 2010 13:42:20 --

(Оффтоп)

rishelie в сообщении #310179 писал(а):

может внести проект в ГД, чтобы узаконить АС? :)))

Что там от аксиомы выбора останется после второго чтения? Право каждого депутата выбрать себе нужную сумму из госбюджета

[master]

(Оффтоп)

Хм.
Прямая. Пусть на прямой через равные промежутки отмечены точки. Пусть количество отмеченых точек на прямой $A$.На прямой отложен луч количество отмеченых точек на луче $B$. $A>B$

[rishelie]

Профессор Снэйп в сообщении #310180 писал(а):

Надо ещё подумать. Или литературу почитать

искать и читать влом, легче подумать :))
и я вот подумал - а зачем что-то выбирать, если можно взять совокупность как целое? :)
допустим, множество $X$ таково, что для любого ординала $\alpha$ существует инъекция из $\alpha$ в $X$.
это означает, что в $X$ можно определять вполне упорядоченные подмножества типа $\alpha$, а иначе говоря, существуют пары $(Y,<)$, где $<$ является вполне упорядочением на $Y\subseteq X$ порядкового типа $\alpha$.
Отлично! Пусть $X_\alpha$ - множество всех пар $(Y,<)$ типа $\alpha$.
Ясно, что все $X_\alpha$ не пусты и что они попарно различны (ведь разные ординалы порядково неизоморфны).

Далее. Принимая пару по определению Куратовского, т.е. $(Y,<)=\{\{Y\},\{Y,<\}\}$, и замечая, что $Y\in {\rm Exp}(X)$, а $<\in{\rm Exp}(X^2)$, а также полагая $A={\rm Exp}(X)\cup{\rm Exp}(X^2)$, получаем, что $(Y,<)\in{\rm Exp}({\rm Exp}(A))$ и, следовательно, $X_\alpha\subseteq{\rm Exp}({\rm Exp}(A))$. Конструкция хоть и многоэтажная, но, тем не менее, это есть множество по аксиомам ZF.

Теперь положим

$$\Phi(\alpha,Y)=(\alpha\in{\rm Ord})(Y=X_\alpha)$$

Это --- определяемое инъективное отображение из собственно класса ${\rm Ord}$ всех ординалов в множество ${\rm Exp}({\rm Exp}({\rm Exp}(A)))$ :)))
Но область значений нашего определяемого отображения $\Phi$ является также множеством по аксиоме выделения, как определяемая часть множества ${\rm Exp}({\rm Exp}({\rm Exp}(A)))$.
Тогда $\Psi(Y,\alpha)=\Phi(\alpha,Y)$ определяет биективное отображение с некоторого множества на класс ординалов. А отсюда будет следовать, что ${\rm Ord}$ --- множество. Противоречие, ибо если ${\rm Ord}$ --- множество, то существует ординал $\alpha={\rm Ord}$, не принадлежащий ему (аксиома фундирования).
Уфф..
Надеюсь, тут нет дыр?

-- Пт апр 16, 2010 19:25:03 --

Кстати, без АС класс кардиналов вполне себе может быть множеством, поэтому пришлось громоздить конструкцию из вполне упорядоченных множеств, хотя изначально (если кто успел прочитать ) я строил доказательство на множествах $X_\tau$, состоящих из подмножеств $X$ мощности $\tau$.

[Профессор Снэйп]

Кстати, да. Второй день ищу подвох и не вижу. По ходу, всё правильно

Допустим, любые два множества сравнимы по мощности. Тогда либо каждое множество меньше либо равно по мощности некоторого ординала, либо существует множество $X$, такое что любой ординал инъективно вкладывается в $X$. В первом случае справедлива теорема Цермело и, следовательно, аксиома выбора. Во втором случае сопоставляем каждому ординалу $\alpha$ множество пар $\langle Y, <^Y_\alpha \rangle$, таких что $Y \subseteq X$ и $<^Y_\alpha$ --- такой линейный порядок на $Y$, что $\langle Y, <^Y_\alpha \rangle \cong \langle \alpha, \in \rangle$. Получаем, что существуют множество $Z \subseteq \mathcal{P}(\mathcal{P}(X) \times \mathcal{P}(X^2))$ и формула (языка теории множеств) $\Phi(x,y)$, такая что

$$ \mathrm{ZF} \vdash (\forall \alpha \text{ --- ординал})(\exists ! z \in Z) \Phi(\alpha, z) $$

и

$$ \mathrm{ZF} \vdash \forall \alpha \forall \beta \forall z (\Phi(\alpha, z) \mathop{\&} \Phi(\beta, z) \rightarrow \alpha = \beta) $$

Отсюда по аксиоме подстановки существует множество всех ординалов

$$ \mathrm{Ord} = \{ \alpha : (\exists z \in Z)\Phi(\alpha, z) \} $$

Но тогда $\bigcup \mathrm{Ord} \cup \{ \bigcup \mathrm{Ord} \}$ --- ординал, не принадлежащий $\mathrm{Ord}$. Противоречие.

Кто видит в этом рассуждении ошибку, пусть скажет. Я ошибки не вижу и единственное, что могу сказать: "Браво, rishelie!"

[Профессор Снэйп]

P. S. Единственное, что с ходу вызывает сомнение: верно ли, что для различных ординалов $\alpha \neq \beta$

$$ \mathrm{ZF} \vdash \langle \alpha, \in \rangle \not\cong \langle \beta, \in \rangle? $$

Попробую вспомнить, как оно всё.

Множество называется транзитивным, если каждый его элемент является его подмножеством. Ординалом называется транзитивное множество с транзитивными элементами.

Ниже до конца поста рассуждаем исключительно в ZF, не используя аксиому выбора.

Утв. 0: Элементы ординалов --- ординалы.

Доказательство. Пусть $\alpha$ --- ординал и $\beta \in \alpha$. Тогда $\beta$ транзитивно. Если $\gamma \in \beta$, то $\gamma \in \alpha$ и $\gamma$ транзитивно, так что элементы $\beta$ тоже транзитивны.

Утв. 1: Для любых двух ординалов $\alpha$, $\beta$ либо $\alpha \in \beta$, либо $\alpha = \beta$, либо $\beta \in \alpha$.

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

Пусть $\alpha$ --- ординал, не сравнимый с каким-то ординалом $\beta$. Если $\alpha$ содержит элементы, не сравнимые с каким-то ординалом, то можно взять $X \subseteq \alpha$, состоящее из таких элементов и в $X$ по аксиоме регулярности выбрать элемент, не содержащий элементов $X$, после чего рассмотреть этот элемент в качестве $\alpha$. Таким образом, можно считать, что любой элемент $\alpha$ сравним с любым ординалом. Если для какого-то $\gamma \in \alpha$ выполнено $\beta \in \gamma$ или $\beta = \gamma$, то $\beta \in \alpha$, чего не может быть. Значит, $\alpha \subseteq \beta$. В силу $\alpha \neq \beta$ и аксиомы регулярности существует $\gamma \in \beta \setminus \alpha$, такой что $\gamma \cap (\beta \setminus \alpha) = \varnothing$. По выбору $\gamma$ имеем $\gamma \subseteq \alpha$. Пусть $\delta \in \alpha$. Если $\gamma \in \delta$ или $\gamma = \delta$, то $\gamma \in \alpha$, чего не может быть. Значит, $\delta \in \gamma$. Таким образом, $\alpha \subseteq \gamma$, $\alpha = \gamma$ и $\alpha \in \beta$. Противоречие.

Утв. 2: Если $\alpha$ --- ординал, то $\langle \alpha, \in \rangle$ --- вполне упорядоченное множество.

Доказательство. Предыдущее утверждение + определение ординала + аксиома регулярности.

Утв. 3: Если $\alpha$ и $\beta$ --- различные ординалы, то $\langle \alpha, \in \rangle \not\cong \langle \beta, \in \rangle$.

Доказательство. По утверждению 1 один из наших ординалов является элементом другого. Пусть, для определённости, $\alpha \in \beta$. Пусть $f : \beta \to \alpha$ --- изоморфизм ВУМов. Пусть $\gamma$ --- Наименьший ординал, такой что $f(\gamma) \neq \gamma$. Получаем очевидное противоречие...

Вроде всё в порядке, аксиому выбора нигде не использовал

-- Пн апр 19, 2010 06:00:21 --

Ха, так это что получается?! Если аксиома выбора не верна, то существует ординал, не сравнимый по мощности с каким-то множеством.

А чему может быть равен наименьший такой ординал. У меня есть подозрение, что можно предложить модель ZF, в которой наименьший такой ординал будет равен $\omega = \aleph_0$. Надо подумать...

-- Пн апр 19, 2010 06:07:27 --

Но если этот ординал счётен, то должно существовать бесконечное множество, которое меняет мощность при добавлении одного элемента. Чудно...

-- Пн апр 19, 2010 06:09:54 --

А, ну да. Это как раз и будет множество, бесконечное в смысле "неравномощно натуральному числу", но не бесконечное в смысле "равномощно собственному подмножеству". Вроде при отрицании аксиомы выбора такие штуки могут вылазить.

[master]

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

[Профессор Снэйп]

Да, количества --- это и есть кардинальные числа При этом совершенно не важно, через равные промежутки отмечены точки или через неравные

[master]

Прямая. Пусть на прямой через равные промежутки отмечены точки. Пусть количество отмеченых точек на прямой $A$.На прямой отложен луч количество отмеченых точек на луче $B$. $A>B$(отмечены соотвественно на всей прямой и промежутки конечные). утверждени верно? или доказывать.

[Профессор Снэйп]

master в сообщении #311113 писал(а):

Прямая. Пусть на прямой через равные промежутки отмечены точки. Пусть количество отмеченых точек на прямой $A$.На прямой отложен луч количество отмеченых точек на луче $B$. $A>B$(отмечены соотвественно на всей прямой и промежутки конечные). утверждени верно? или доказывать.

Шо сие за бред?

И подобное сообщение уже есть. Не нужно его дублировать.

[master]

Бред так бред

[rishelie]

master в сообщении #311121 писал(а):

Бред так бред

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

-- Пн апр 19, 2010 12:49:53 --

Профессор Снэйп в сообщении #311076 писал(а):

Ха, так это что получается?! Если аксиома выбора не верна, то существует ординал, не сравнимый по мощности с каким-то множеством.

А чему может быть равен наименьший такой ординал. У меня есть подозрение, что можно предложить модель ZF, в которой наименьший такой ординал будет равен $\omega = \aleph_0$. Надо подумать...

че-то я вот тут не совсем....
мы показали: если любые два множества сравнимы по мощности, то АС верна. Соответственно, если неАС, то существуют два множества, несравнимые по мощности. Почему это должны быть ординалы? Или хотя бы одно из них?

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

-- Пн апр 19, 2010 12:53:50 --

кстати, не исключено, что утверждение о том, что $\omega$ - единственный бесконечный кардинал, не противоречит ZF. и даже наверно не противоречит AD (аксиоме детерминированности). впрочем, это вроде банальщина из учебников?