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

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

patzer2097 в сообщении #308886 писал(а):

Вы проводите трансфинитную индукцию по кардинальным числам, я правильно понял? А так разве можно?

Да ну почему нельзя? Кардиналы --- они все ординалы, а вести трансфинитную индукцию по ординалам сам Бог велел

[Someone]

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

вот тут и работает аксиома выбора

Она у Вас ещё раньше работает - в "проглоченном" предположении, что все бесконечные кардиналы - алефы.

[patzer2097]

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

patzer2097 в сообщении #308886 писал(а):

Вы проводите трансфинитную индукцию по кардинальным числам, я правильно понял? А так разве можно?

Да ну почему нельзя? Кардиналы --- они все ординалы, а вести трансфинитную индукцию по ординалам сам Бог велел

Хм.. Но трансфинитная индукция - она же работает на вполне упорядоченных множествах?

[RIP]

Множество $\mathfrak n+1$ вполне упорядочено. Соответственно, вполне упорядочено и его подмножество, которое состоит только из кардиналов. Вот на нём и используем трансфинитную индукцию.

[мат-ламер]

Так ли я понял дискуссию, что кардинал - это класс (равномощных множеств), а совокупность кардиналов - это уже множество, которое можно вполне упорядочить (и по которому можно вести трансфинитную индукцию)?

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

мат-ламер в сообщении #309038 писал(а):

Так ли я понял дискуссию, что кардинал - это класс (равномощных множеств), а совокупность кардиналов - это уже множество, которое можно вполне упорядочить (и по которому можно вести трансфинитную индукцию)?

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

Кардиналом называется такой ординал, который не равномощен никакому своему элементу.

Теорема (принцип трансфинитной индукции для ординалов) Пусть $\Phi(x)$ --- произвольное свойство множеств и для любого ординала $\alpha$ выполнено

$$ (\forall \beta \in \alpha)\Phi(\beta) \rightarrow \Phi(\alpha) $$

Тогда свойство $\Phi$ выполнено на всех ординалах.

Следствие (принцип трансфинитной индукции для кардиналов) Пусть $\Psi(x)$ --- свойство множеств и для любого кардинала $\alpha$ справедливо

$$ (\forall \beta \text{ --- кардинал})(\beta < \alpha \rightarrow \Psi(\beta)) \rightarrow \Psi(\alpha) $$

Тогда свойство $\Psi$ выполнено на всех кардиналах.

Доказательство. Рассмотрим $\Phi(x) = \Psi(x) \vee (x \text{ --- не кардинал})$ и применим теорему.

-- Вт апр 13, 2010 20:31:14 --

patzer2097 в сообщении #309017 писал(а):

Но трансфинитная индукция - она же работает на вполне упорядоченных множествах?

И на классе ординалов тоже. См. выше.

[Padawan]

patzer2097
Любое множество кардиналов вполне упорядочено по величине

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

Padawan в сообщении #309055 писал(а):

patzer2097
Любое множество кардиналов вполне упорядочено по величине

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

[rishelie]

можно :) их же можно ординалами занумеровать, те самые алефы.
вообще можно по любому вполне упорядоченному классу/множеству

[rishelie]

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

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

вот тут и работает аксиома выбора

Она у Вас ещё раньше работает - в "проглоченном" предположении, что все бесконечные кардиналы - алефы.

хм.. я пользуюсь определением, где кардинал - это наименьший из равномощных ординалов :)
т.е. у меня кардиналы - изначально алефы.
и топиковое соотношение доказываю именно для них :)
или Вы имеете ввиду рекурсивное построение отображения $\aleph:{\rm Ord}\to {\rm Card}$? так оно вроде не требует АС.
впрочем, это уже мелочи

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

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

кардинал - это наименьший из равномощных ординалов :)
т.е. у меня кардиналы - изначально алефы.
и топиковое соотношение доказываю именно для них

Да, именно так Кардинал --- наименьший (по отношению принадлежности) среди равномощных ординалов. Сравнение по мощности --- первичное понятие, сама мощность --- вторичное, вводимое через упомянутое сравнение.

Кардиналы можно занумеровать через ординалы. Традиция нумерует только бесконечные кардиналы; это слегка нелогичнго, но неудобств не доставляет. Если действовать последовательно, то наименьший бесконечный кардинал --- $\aleph_\omega$, наименьший бесконечный несчётный --- $\aleph_{\omega \cup \{ \omega \}}$ и т. д. Но вместо $\aleph_\omega$ пишут $\aleph_0$, вместо $\aleph_{\omega \cup \{ \omega \}}$ --- $\aleph_1$ (иногда $\omega_1$, в Новосибирске, я вообще заметил, буква алеф непопулярна) и так далее...

Каждый кардинал имеет номер и по этому номеру, если кому-то будет угодно, можно вести индукцию. Правда не знаю ни одного утверждения, где бы эта индукция была бы действительно необходима. В этой теме вроде возникла идея такой индукции, но она, конечно же, не по существу. Теорема о том, что аксиома выбора $\Leftrightarrow$ лемме Цорна $\Leftrightarrow$ теореме о равенстве $|A^2| = |A|$ для всех бесконечных $A$, не привлекает индукцию в явном виде.

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

-- Ср апр 14, 2010 18:24:23 --

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

[rishelie]

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

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

берем произвольное множество $X$. оно сравнимо по мощности с любым кардиналом - либо вкладывается в него инъекцией, либо поглощает его (т.е. существует инъекция с данного кардинала в $X$). первый случай сразу дает вполне упорядочение $X$.
если же любой кардинал вкладывается в $X$, то нужно построить инъективное отображение с класса ординалов в $X$.
думаю, тут придется применять рекурсию по кардиналам.
допустим, что для всех кардиналов $k<n$ построена монотонно возрастающая цепь инъекций $f_k:k\to X$. нужно построить $f_n$.
если $n$ - предельный кардинал, то полагаем $f_n=\cup\{f_k\}$
если $n=k+1$ (сложение на кардиналах) для некоторого $k$, то берем произвольную инъекцию $f:n\to X$ и обозначаем область значений $f$ через $Y\subseteq X$. Теперь из $Y$ удалим образ $f_k$, полагая $Z=Y\setminus f_k[k]$.
Множество $Z$ имеет мощность $n$ (тут ведь не нужно использовать АС, не так ли?).
Множество $n\setminus k$ также имеет мощность $n$. Следовательно, существует биекция $g:n\setminus k\to Z$. Но тогда $f_k\cup g$ --- инъекция из $n$ в $X$, содержащая все инъекции $f_j$, $j<n$.
Итак, можно построить класс инъекций $f_k$ для всех кардиналов $k$, обладающих тем свойством, что они линейно упорядочены по вложению, т.е. образуют цепь. Тогда объединение этой цепи будет инъективным отображением из класса ординалов в $X$. Противоречие.

вот что на ночь глядя лезет в голову :)

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

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

Тогда объединение этой цепи будет...

Э-э-э... Аксиома объединения утверждает, что для любого множества $x$ существует множество $\bigcup x$. А Вы тут объединение целого класса рассматриваете, который множеством не является

И вообще, о какой такой "инъекции" класса (в множество $X$) Вы говорите? Инъекция --- разновидность функции, функция --- подмножество декартова произведения, отображать, вообще говоря, можно лишь множества

Хотя если удастся построить некое утверждение $\Phi(x,y)$, такое что

$$ \mathrm{ZF} \vdash \forall x(x \text{ --- ординал} \rightarrow \exists ! y(y \in X \mathop{\&} \Phi(x,y)) $$

и

$$ \mathrm{ZF} \vdash \forall x_1 \forall x_2 \forall y (\Phi(x_1,y) \mathop{\&} \Phi(x_2,y) \rightarrow x_1 = x_2), $$

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

-- Чт апр 15, 2010 13:49:51 --

rishelie, Вы, по ходу, ещё кардиналы с ординалами путаете? Что у Вас за "предельный кардинал" такой или "сложение на кардиналах" (в том месте, где Вы прибавляете единицу). Пока что буду пытаться под Вашими "кардиналами" подразумевать ординалы

-- Чт апр 15, 2010 13:59:09 --

Нет, всё-таки кардиналы... Под "предельным кардиналом" имелся в виду кардинал $\aleph_\alpha$ с предельным ординалом $\alpha$, под суммой $\aleph_\alpha + 1$ --- кардинал $\aleph_{\alpha+1}$, так?

-------------------------------------------

Ага, нашёл существенный косяк!

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

Множество $Z$ имеет мощность $n$ (тут ведь не нужно использовать АС, не так ли?).
Множество $n\setminus k$ также имеет мощность $n$. Следовательно, существует биекция $g:n\setminus k\to Z$. Но тогда $f_k\cup g$ --- инъекция из $n$ в $X$, содержащая все инъекции $f_j$, $j<n$.

Аксиомой выбора Вы всё-таки пользуетесь

То, что $Z$ имеет мощность $n$, аксиому выбора... я даже затрудняюсь с ходу ответить, привлекает или нет. Кардинальная арифметика без аксиомы выбора --- вещь довольно противная. Но это даже и не важно. Далее ведь Вы всё-равно выбираете $g$

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

И всё-таки интересно (хотя и не спасает предложенное rishelie рассуждение), верно ли, что если $\alpha < \beta$ --- бесконечные кардиналы, то $|\beta \setminus \alpha| = \beta$?

Имеем $\beta = \alpha \cup (\beta \setminus \alpha)$. Если бы было верно $|X \cup Y| = \max \{ |X|, |Y| \}$ (в ситуации, когда хотя бы одно из множеств $X$, $Y$ бесконечно), то всё было бы окей. Но я знаю доказателство равенства $|X \cup Y| = \max \{ |X|, |Y| \}$ лишь исходя из теоремы о мощности квадрата бесконечного множества, а она эквивалентна аксиоме выбора и ей пользоваться нельзя.

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

1) Любые два ординала сравнимы по мощности. Это просто в ZF так, кардиналы --- это ординалы, для двух различных ординалов в ZF верно, что один является элементом другого.

2) Если $\alpha$ ---бесконечный кардинал и $|X| \leqslant |Y| = \alpha$, то $|X \cup Y| = \alpha$. Действительно, чередуя чётные и нечётные элементы, в $\alpha$ можно выделить две копии $\alpha$. Далее по теореме Кантора-Бернштейна. Аксиома выбора вроде как не нужна.

3) У нас $\alpha < \beta$ и между $\alpha$ и $\beta$ нет промежуточных кардиналов. Имеем $|\beta \setminus \alpha| \leqslant \beta$. Если неравенство строгое, то $|\beta \setminus \alpha| \leqslant \alpha$ и противоречие с предыдущим пунктом.

Так что этот момент у rishelie вроде нормальный. Но далее, увы, $g$ всё равно выбирается...

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

[rishelie]

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

со сложением я, действительно, глупость написал, имея ввиду, что $n=k^+$ (следующий за $k$ кардинал), либо это и будет $\aleph_{\alpha+1}$.

выбор $g$ я вообще-то хотел произвести по теореме Кантора-Бернштейна, но подстраиваться под нее было долго, и написал просто о существовании, уповая на то, что раз уж у нас используются инъекции с кардиналов, то они переносят вполне упорядочение на рассматриваемые множества и, значит, дают акиому выбора для мощностей порядка $n$.
а ведь теорема Кантора-Бернштейна явным образом строит биекцию без использования акиомы выбора.
но произвольный выбор все равно остается - это выбор $f:n\to X$. Однако, этот выбор однократный, и если он вмонтирован в определение $\Phi(x,y)$, то АС тут ни при чем.

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