Ординальные числа

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

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

Пусть $A$, $B$, $C$ --- линейно упорядоченные множества. Доказать, что:

Пусть $A$ и $B$ --- линейно упорядоченные множества. Доказать, что если $A \simeq B$, то $\left|A\right| = \left|B\right|$, но обратное неверно.

Доказать, что множество из $n$ элементов можно линейно упорядочить $n!$ способами.

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

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

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

Доказать, что для любого линейно упорядоченного множества $A$ и любых $a, b \in A$:

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

Доказать, что бесконечное линейно упорядоченное множество $A$ имеет порядковый тип $\omega$ тогда и только тогда, когда оно удовлетворяет следующим условиям:

Доказать, что бесконечное линейно упорядоченное множество имеет порядковый тип $\omega$ тогда и только тогда, когда все его начальные отрезки конечны.

Доказать, что любое счетное линейно упорядоченное множество $A$ имеет порядковый тип $\eta$ тогда и только тогда, когда $A$ удовлетворяет следующим условиям:

Доказать, что всякое счетное линейно упорядоченное множество подобно некоторому подмножеству множества $\mathbb {Q}$ рациональных чисел.

Пусть $A$ --- линейно упорядоченное множество, содержащее не менее двух элементов, $B = A \cup A^{2} \cup \ldots \cup A^{n} \cup \ldots$ Положим для любых $x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m} \in A$ $(1 \leq n, m)$

Доказать, что:

Доказать, что порядковый тип любого интервала (не сегмента) действительных чисел есть $\lambda$.

Подмножество $B$ линейно упорядоченного множества $A$ с порядком $\leq$ называется плотным в $A$, если для любых $a_{1}, a_{2} \in A$ существует $b \in B$ такое, что $a_{1} \leq b \leq a_{2}$ или $a_{2} \leq b \leq a_{1}$. Доказать, что если $A$ содержит счетное плотное в $A$ подмножество, то $A$ подобно некоторому подмножеству множества действительных чисел $\mathbb {R}$ с естественным порядком.

Показать, что $(\alpha^{*})^{*} = \alpha$ для любого порядкового типа $\alpha$.

Показать, что $\pi^{*} = \pi$, $\eta^{*} = \eta$, $\lambda^{*} = \lambda$, $\omega^{*} \neq \omega$.

Доказать, что:

Привести пример порядковых типов $\alpha$ и $\beta$ таких, что

Доказать, что:

Привести пример порядковых типов $\alpha$ и $\beta$ таких, что

Доказать, что:

Построить множества порядковых типов $\omega^{2}, \omega^{3}, \omega^{4}, \ldots$

Пусть $J$ и $I$ --- линейно упорядоченные множества, $\left\{ B_{i}\right\}_{i \in I}$ --- семейство попарно непересекающихся подмножеств множества $J$ такое, что $\bigcup_{i \in I} B_{i} = J$. Доказать, что если $\overline{\overline{J}} = \sum_{i \in I} \overline{\overline{B_{i}}}$, то для любого семейства порядковых чисел $\left\{ \alpha_{j}\right\}_{j \in J}$ имеем $\sum_{j \in J} \alpha_{j} = \sum_{i \in I} \left(\sum_{j \in B_{i}} \alpha_{j}\right)$.

Доказать, что $\alpha \cdot \beta = \sum_{b \in B} \alpha_{b}$, где $\alpha_{b} = \alpha$ для всех $b \in B$ и $\overline{\overline{B}} = \beta$.

Доказать, что:

Доказать, что:

Являются ли вполне упорядоченными следующие множества:

Доказать, что:

Доказать, что если $A \sim B$ и $A$ вполне упорядочено, то $B$ можно вполне упорядочить так, чтобы было $A \simeq B$.

Показать, что если $A$ --- вполне упорядоченное множество, то у каждого элемента множества $A$, кроме наибольшего, имеется непосредственно следующий за ним элемент (см. задачу I.5.11).

Можно ли во вполне упорядоченном множестве выделить бесконечную убывающую цепь элементов $x_{1} > x_{2} > x_{3} > \ldots$?

Доказать, что линейно упорядоченное множество вполне упорядочено тогда и только тогда, когда оно не содержит подмножества типа $\omega^{*}$.

Пусть $A$ --- вполне упорядоченное множество. Доказать, что не существует такого монотонного взаимно однозначного соответствия $f: A \rightarrow A$, чтобы для некоторого элемента $a \in A$ было $f(a) < a$.

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

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

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

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

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

Пусть $A$ --- вполне упорядоченное множество, $B \subseteq A$ и для любого элемента $x \in A$ множество $B$ удовлетворяет условию: если $A_{x} \subseteq B$, то $x \in B$. Доказать, что $B = A$ (принцип трансфинитной индукции).

Пусть $\alpha$, $\beta$ --- произвольные порядковые числа. Доказать, что:

Пусть $W_{\alpha } = \left\{ \beta \mid \beta < \alpha \right\}$, где $\alpha$ и $\beta$ --- порядковые числа. Показать, что $\overline{\overline{W_{\alpha }}} = \alpha$.

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

Доказать, что для любого множества порядковых чисел $S$:

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

Доказать, что $\alpha + 1$ есть порядковое число, непосредственно следующее за $\alpha$ (см. задачу I.5.11).

Доказать, что для любого порядкового числа $\alpha$ имеет место одно и только одно из утверждений:

1. $\alpha = 0$;

2. множество $\left\{ \beta \mid \beta \text{ --- порядковое число и } \beta < \alpha \right\}$ имеет максимальный элемент;

3. $\alpha$ — предельное порядковое число.

Доказать, что любое порядковое число представимо в виде $\alpha + n$, где $\alpha$ есть предельное порядковое число или $0$, $n$ --- натуральное число.

Доказать, что:

Пусть $I$ и $\left\{ A_{i}\right\}_{i \in I}$ линейно упорядочены. Доказать, что если $A_{i} \neq \emptyset$ и $\sum_{i \in I} \overline{\overline{A_{i}}}$ есть порядковое число, то $I$ и все $A_{i}$ вполне упорядочены.

Доказать, что:

Привести пример порядковых чисел $\alpha$, $\beta$ и $\gamma$ таких, что

Доказать, что:

Пусть $\beta \leq \alpha$. Порядковое число $\gamma$ называется разностью $\alpha$ и $\beta$ и обозначается через $\alpha - \beta$, если $\alpha = \beta + \gamma$.

Доказать, что:

Доказать, что:

Доказать, что для любых порядковых чисел $\alpha_{0}$ и $\alpha_{1}$, если $\alpha_{0} \neq 0$ и $\alpha_{1} \neq 0$, то существуют натуральное число $n$ и порядковые числа $\alpha_{2}, \ldots , \alpha_{n}, \beta_{1}, \beta_{2}, \ldots , \beta_{n}$ такие, что $\alpha_{1} > \alpha_{2} > \ldots > \alpha_{n} > 0$ и $\alpha_{0} = \alpha_{1} \cdot \beta_{1} + \alpha_{2}$, $\alpha_{1} = \alpha_{2} \cdot \beta_{2} + \alpha_{3}, \ldots , \alpha_{n-2} = \alpha_{n-1} \cdot \beta_{n-1} + \alpha_{n}$, $\alpha_{n-1} = \alpha_{n} \cdot \beta_{n}$ (алгоритм Евклида).

Пусть свойство $P$ таково, что для любого ординального числа $\alpha$ из того, что все ординальные числа $\beta < \alpha$ обладают свойством $P$, следует, что $\alpha$ обладает свойством $P$. Доказать, что все ординальные числа обладают свойством $P$ (принцип трансфинитной индукции для ординальных чисел).

Доказать, что для любых порядковых чисел $\alpha$ и $\beta$ существует и единственно $\alpha^{\beta }$.

Построить множество порядкового типа $\omega^{\omega }$.

Доказать, что:

Доказать, что:

Множество $S$ называется транзитивным, если отношение

вполне упорядочивает $S$, $\emptyset \in S$ и если из $X \in Y$, $Y \in S$ следует $X \in S$. Доказать, что для любого порядкового числа $\alpha \geq 0$ существует и единственно транзитивное множество, упорядоченное по типу $\alpha$.

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

1. Аксиома выбора. Пусть $X_{a}$ — непустое множество для любого $a \in A$. Тогда существует функция выбора $f: A \rightarrow \bigcup_{a \in A} X_{a}$ такая, что $f(a) \in X_{a}$ для любого $a \in A$. Доказать, что каждое из следующих утверждений эквивалентно аксиоме выбора.

2. Лемма Цорна. Частично упорядоченное множество, каждое из линейно упорядоченных подмножеств которого имеет верхнюю грань, содержит максимальный элемент.

3. Принцип максимальности Куратовского–Хаусдорфа. Каждая цепь частично упорядоченного множества содержится в некоторой максимальной цепи.

4. Аксиома Цермело. Для любого семейства $S$ непустых попарно непересекающихся множеств существует такое множество $C$, что $A \cap C$ для каждого $A \in S$ состоит ровно из одной точки.

5. Теорема Цермело. Каждое множество можно вполне упорядочить.

6. Лемма Тейхмюллера–Тьюки. Каждое семейство множеств, имеющее конечный характер, обладает максимальным элементом. (Семейство $S$ множеств имеет конечный характер, если оно удовлетворяет условию: $X \in S \Leftrightarrow$ каждое конечное подмножество множества $X$ принадлежит $S$.)

Пусть $A$ --- частично упорядоченное множество, в котором каждая цепь имеет верхнюю грань, и $a \in A$. Доказать, что существует максимальный элемент $m \in A$ такой, что $m \geq a$.

Пусть $A$ --- множество подмножеств множества $B$ такое, что для каждой цепи $C$ (порядок по включению) объединение множеств из $C$ принадлежит $A$. Доказать, что тогда $A$ имеет максимальный элемент.

Доказать, что для всякого частичного порядка $R$ на множестве $A$ существует линейный порядок $L$ на множестве $A$ такой, что $R \subseteq L$.