Тема 16

Ординални числа. Основни свойства. Трансфинитна индукция.

---

страницата се нуждае от дописване/преглеждане

---

Ординални числа

Първо ще си припомним дефиницията за транзитивно множество:
Дефиниция(транзитивно множество):

(1)

\begin{align} \mathrm{Trans}(x) \rightleftharpoons \forall y\forall z(y \in z \And z \in x \Rightarrow y \in x) \end{align}

Дефиниция:

(2)

\begin{array} {rcc} \mathrm{EWO}(x) &\rightleftharpoons& \forall y\forall z(y \in x \And z \in x \Rightarrow y \in z \lor y = z \lor z \in y) \\ & & \And \\ & & \forall u(u \ne \varnothing \And u \subseteq x \Rightarrow \exists y (y \in u \And y \cap u = \varnothing)) \end{array}

Дефиниция(Ординално число):

(3)

\begin{align} \mathrm{Ord}(x) \rightleftharpoons \mathrm{Trans}(x) \And \mathrm{EWO}(x) \end{align}

Забележка: За напред ще използваме гръцки букви за ординални числа, и под $\forall \alpha \varphi(\bar u, \alpha)$ ще разбираме $\forall \alpha (\mathrm{Ord} (\alpha) \And \varphi(\bar u, \alpha))$ - т.е кванторите по гръцки букви са квантори по ординални числа (същото и за $\exists$).

Дефиниция(операция по-малко): $\alpha < \beta \rightleftharpoons \alpha \in \beta$
Дефиниция(по-малко или равно): $\alpha \le \beta \rightleftharpoons \alpha < \beta \lor \alpha = \beta$

Свойства

Ще докажем следните 12 свойства за ординални числа:
Св1:

• $\alpha \notin \alpha$
• $\forall x \lnot (x \in \alpha \And \alpha \in x)$
• $(\forall x \in \alpha)(\forall y \in \alpha)\lnot(x \in y \And y \in x)$

Св2: $\alpha < \beta \And \beta < \gamma \Rightarrow \alpha < \gamma$
Св3:

• $\lnot(\alpha < \alpha)$
• $\alpha < \beta \Rightarrow \lnot (\beta < \alpha)$

Св4:

• $\mathrm{Ord}(\mathrm{S}(\alpha))$
• $\alpha < \mathrm{S}(\alpha)$
• $\lnot \exits \beta ( \alpha < \beta \And \beta < \mathrm{S}(\alpha))$

Св5: $x \in \alpha \Rightarrow \mathrm{Ord}(x)$
Св6: $x \subseteq \alpha \And \mathrm{Trans}(x) \Rightarrow x = \alpha \lor x \in \alpha$
Св7: $\alpha \le \beta \iff \alpha \subseteq \beta$
Св8: $\alpha < \beta \lor \alpha = \beta \lor \beta < \alpha$
Св9: $\alpha < \beta \iff \mathrm{S}(\alpha) \le \beta$
Св10: $(\forall y \in x)\mathrm{Ord}(y) \Rightarrow \mathrm{EWO}(x) \And \mathrm{Ord}(\cup x)$
Св11: $(\forall y \in x)\mathrm{Ord}(y) \Rightarrow \langle x, \in_x \rangle$ е добра наредба¹
Св12: $(\forall y \in x)\mathrm{Ord}(y) \Rightarrow (\cup x \le \beta \iff (\forall \alpha \in x)(\alpha \le \beta))$

Доказателства на свойствата

Св1:

• $\alpha \notin \alpha$

Да допуснем противното - именно, че $\alpha \in \alpha$. Така получаваме $\{ \alpha \} \subseteq \alpha$. Сега използваме второто условие за EWO и получаваме $\exists y ( y \in \{ \alpha \} \And y \cap \{ \alpha \} = \varnothing)$. От $y \in \{ \alpha \}$ получаваме $y = \alpha$. И така получихме $\alpha \in y \And \alpha \in \{ \alpha \}$ от където $\alpha \in y \cap \{ \alpha \}$. Противоречие!

• $\forall x \lnot (x \in \alpha \And \alpha \in x)$

Допускаме противното - именно, че $\exists x(x \in \alpha \And \alpha \in x)$. Тогава от $\alpha \in x \in \alpha$ и $\mathrm{Trans}(\alpha)$ получаваме $\alpha \in \alpha$, което противоречи със горното свойство.

• $(\forall x \in \alpha)(\forall y \in \alpha)\lnot(x \in y \And y \in x)$

Да допуснем противното - именно, че съществуват $x, y \in \alpha : x \in y \And y \in x$. Да си образуваме $\{ x, y \} \subseteq \alpha$. Използваме второто условие от EWO и получаваме $\exists z ( z \in \{ x, y \} \And z \cap \{ x, y \} = \varnothing)$.

1. $z \in x \Rightarrow y \in x \And y \in \{ x ,y \} \Rightarrow y \in z \cap \{ x, y \}$ - противоречие!
2. $z \in y \Rightarrow x \in y \And x \in \{ x ,y \} \Rightarrow x \in z \cap \{ x, y \}$ - противоречие!

Св2: Това свойство следва директно от транзитивността на ординалните числа
Св3: Това свойство е същото като първото и второто от свойство 1, но записани чрез <
Св4:

• $\mathrm{Ord}(\mathrm{S}(\alpha))$

Нека $\mathrm{Ord}(\alpha)$. Имаме $\mathrm{S}(\alpha) = \alpha \cup \{ \alpha \}$
$\mathrm{Trans}(\mathrm{S}(\alpha))$ сме го доказвали тук , когато въведохме $\mathrm{Trans}$.
Сега да докажем $\mathrm{EWO}(\mathrm{S}(\alpha))$.
Нека $x, y \in \mathrm{S}(\alpha)$. Ще проверим, че $x \in y \lor x = y \lor y \in x$.

1. $x, y \in \alpha$ - вярно от $\mathrm{EWO}(\alpha)$
2. $x, y \in \{ \alpha \}$ - тогава $x = y = \alpha$
3. $x \in \alpha \And y \in \{ \alpha \}$ - тогава $x \in \alpha = y$
4. $y \in \alpha \And x \in \{ \alpha \}$ - тогава $y \in \alpha = x$

Нека $\varnothing \ne u \subseteq \mathrm{S}(\alpha)$. Образуваме си $u' = u \setminus \{ \alpha \}$.

1. $u' = \varnothig$ - тогава $u = \{ \alpha \}$. Сега $\alpha \in u \And \alpha \cap u = \varnothing$ - т.е $\alpha$ е множеството което съществува от второто условие за EWO.
2. $u' \neq \varnothing$. Получаваме $u' \subseteq \alpha$. От $\mathrm{Ord}(\alpha)$ получаваме $\exists y(y \in u' \And y \cap u' = \varnothing)$. Нека $y_0$ е едно такова. Тогава $y_0 \in u$. $y_0 \cap u \subseteq y_0 \cap (u' \cup \{ \alpha \}) = (y \cap u') \cup (y \cap \{ \alpha \}) = y \cap \{ \alpha \}$. Обаче $y_0 \in u' \subseteq \alpha \Rightarrow y \in \alpha \Rightarrow a \notin y$. Т.е получихме $y_0 \cap u = \varnothing$, с което доказахме $\mathrm{EWO}(\mathrm{S}(\alpha))$. Окончателно, от $\mathrm{Trans}(\mathrm{S}(\alpha)) \And \mathrm{EWO}(\mathrm{S}(\alpha))$ получихме $\mathrm{Ord}(\mathrm{S}(\alpha))$

• $\alpha < \mathrm{S}(\alpha)$ - тривиално от дефиницията на $\mathrm{S}$.
• $\lnot \exits \beta ( \alpha < \beta \And \beta < \mathrm{S}(\alpha))$

Допускаме, че съществува $\beta : \alpha < \beta \And \beta < \mathrm{S}(\alpha)$. От $\beta \in \alpha \cup \{ \alpha \}$ имаме:

1. $\beta \in \alpha \Rightarrow \beta < \alpha \Rightarrow \lnot \alpha < \beta$ - противоречие
2. $\beta = \alpha \Rightarrow \lnot \alpha < \beta$ - противоречие

Св5: $x \in \alpha \Rightarrow \mathrm{Ord}(x)$
Нека $x \in \alpha$ е произволен.
Да проверим $\mathrm{Trans}(x)$. Нека $z \in y \And y \in x$. От $\mathrm{Trans}(\alpha)$ получаваме $x, z \in \alpha$. Тогава използваме първото условие от EWO за $\alpha$, от където имаме следните 3 случая: $x \in z \lor x = z \lor x \ni z$.

1. $x = z$ - от условието имаме $x = z \in y \And y \in x \And x, y \in \alpha$ - противоречие с първо свойство
2. $x \in z$ - т.е получава се следния 'цикъл' : $x \in z \in y \in x$. Ще докажем, че това е невъзможно по аналогия с доказателството за несъществуване на цикъл с дължина 2 от свойство 1. $\varnothing \ne \{ x, y, z \} \subseteq \alpha$. От $\mathrm{EWO}(\alpha)$ имаме $\exists v(v \in \{ x, y, z \} \And v \cap \{ x, y, z\} = \varnothing)$.
   1. $v = x$. Тогава имаме $y \in x = v \And y \in \{ x, y, z \} \Rightarrow y \in v \cap \{ x , y, z \}$ - противоречие!
   2. $v = y$. Тогава имаме $z \in y = v \And z \in \{ x, y, z \} \Rightarrow z \in v \cap \{ x , y, z \}$ - противоречие!
   3. $v = z$. Тогава имаме $x \in z = v \And x \in \{ x, y, z \} \Rightarrow x \in v \cap \{ x , y, z \}$ - противоречие!

Окончателно отхвърлихме $x = z \And x \in z$, т.е остава $z \in x$, с което показахме, че $\mathrm{Trans}(x)$.
Сега да проверим $\mathrm{EWO}(x)$.

1. Нека $y, z \in x$. От транзитивността на $\alpha$ получаваме, че $y, z \in \alpha$, от където $y \in z \lor y = z \lor y \ni z$.
2. Нека $\varnothing \ne u \subseteq x$. Тогава $u \subseteq \alpha \Rightarrow \exists y( y \in u \And y \cap u = \varnothing)$.

Т.е изпълнени са и 2те условия на EWO. Окончателно показахме $\mathrm{Trans}(x) \And \mathrm{EWO}(x) \Rightarrow \mathrm{Ord}(x)$.
Св6: $x \subseteq \alpha \And \mathrm{Trans}(x) \Rightarrow x = \alpha \lor x \in \alpha$
Нека $x \subseteq \alpha \And \mathrm{Trans}(x)$. Да си образуваме множеството $u = \alpha \setminus x$

1. $u = \varnothing \Rightarrow x = \alpha$
2. $u \ne \varnothing \And u \subseteq \alpha \Rightarrow \exists y (y \in u \And y \cap u = \varnothing)$. Ще докажем $x = y$, с влагане в 2^те посоки:
   1. $z \in x$. Понеже $z \in x \subseteq \alpha \Rightarrow z \in \alpha \And y \in u \subseteq \alpha \Rightarrow y \in \alpha$. Тогава $y \in z \lor y = z \lor z \in y$. Ще покажем, че $z \in y$ като отхвърлим другите 2 възможности
      1. $y = z \Rightarrow y \in x \Rightarrow y \notin u$ - противоречие!
      2. $y \in z \Rightarrow y \in x \Rightarrow y \notin u$ - противоречие!
   2. $z \in y$. Допускаме, че $z \notin x \Rightarrow z \in u \Rightarrow z \in y \cap u$ - противоречие! Следователно $z \in x$.

С това доказахме, че $x = y$ във втория случай - т.е $y \in u \subseteq \alpha \Rightarrow x \in \alpha$, което се оптивахме да докажем.
Св7: $\alpha \le \beta \iff \alpha \subseteq \beta$
Права посока: Нека $\alpha \le \beta$. Тогава $\alpha \in \beta \lor \alpha = \beta$. При $\alpha = \beta \Rightarrow \alpha \subseteq \beta$. При $\alpha \in \beta$ от транзитивността на $\beta$ следва $\alpha \subseteq \beta$.
Обратна посока: Нека $\alpha \subseteq \beta$. Понеже $\alpha$ е ординално число, тогава $\mathrm{Trans}(\alpha)$ и от предното свойство получаваме $\alpha \in \beta \lor \alpha = \beta \iff \alpha < \beta \lor \alpha = \beta \iff \alpha \le \beta$, с което доказахме исканото.
Св8: $\alpha < \beta \lor \alpha = \beta \lor \beta < \alpha$
Нека образуваме $x = \alpha \cap \beta$. $\mathrm{Trans}(\alpha) \And \mathrm{Trans}(\beta) \Rightarrow \mathrm{Trans}(x)$ - доказвали сме го тук.

• $\mathrm{Trans}(x) \And x \in \alpha \Rightarrow x = \alpha \lor x \in \alpha$
• $\mathrm{Trans}(x) \And x \in \beta \Rightarrow x = \beta \lor x \in \beta$

Разглеждаме 4^те възможни комбинации

	$x = \alpha$	$x \in \alpha$
$x = \beta$	$\alpha = x = \beta$	$\beta = x \in \alpha$
$x \in \beta$	$\alpha = x \in \beta$	$x \in \alpha \cap \beta = x$ - противоречие!

Т.е в 3те случая, които са валидни получихме $\alpha < \beta \lor \alpha = \beta \lor \beta < \alpha$, с което свойството е доказано.

Св9: $\alpha < \beta \iff \mathrm{S}(\alpha) \le \beta$
Права посока: Нека $\alpha < \beta \Rightarrow \alpha \in \beta \Rightarrow \alpha \subseteq \beta \And \{ \alpha \} \subseteq \beta \Rightarrow \mathrm{S}(\alpha) \subseteq \beta \Rightarrow \mathrm{S}(\alpha) \le \beta$.
Обратна посока: Нека $\mathrm{S}(\alpha) \le \beta \Rightarrow \{ \alpha \} \subseteq \beta \Rightarrow \alpha \in \beta \Rightarrow \alpha < \beta$

Св10: $(\forall y \in x)\mathrm{Ord}(y) \Rightarrow \mathrm{EWO}(x) \And \mathrm{Ord}(\cup x)$
Нека $y', y'' \in x$. Тогава от условието $\mathrm{Ord}(y') \And \mathrm{Ord}(y'')$. Всеки 2 ординални числа са сравними от Св8, следователно $y' < y'' \lor y' = y'' \lor y'' < y'$. С това доказахме първата част от EWO.
Нека $\varnothing \ne u \subseteq x$. Образуваме си $u' = u \cap \alpha$.

1. $u' = \varnothing$. В този случай $\alpha \in u \And \alpha \cap u = \varnothing$, следователно $\alpha$ изпълнява 2^ра част на EWO за $u$
2. $u' \ne \varnothing$. Тогава $u' \subseteq \alpha \And \mathrm{EWO}(\alpha) \Rightarrow \exists y (y \in u' \And y \cap u' = \varnothing)$. Нека изберем едно такова $y_0$. Ще докажем, че $y_0 \cap u = \varnothing$. Допускаме противното - именно $\exists z(z \in y_0 \cap u)$. $z \in y \Rightarrow z \notin u \Rightarrow z \notin \alpha \Rightarrow \lnot(z < \alpha) \Rightarrow z = \alpha \lor \alpha < z$.
   1. $z = \alpha \Rightarrow \alpha = z \in y \cap u \And u \subseteq \alpha \Rightarrow \alpha \in \alpha$ - противоречие!
   2. $\alpha \in z \Rightarrow \alpha \in z \in u \subseteq \alpha \Rightarrow \alpha \in \alpha$ - противоречие!

Т.е показахме $\mathrm{EWO}(x)$.
Сега да докажем $\mathrm{Ord}(\cup x)$.

1. $\mathrm{Trans}(\cup x)$ - това е изпълнено, защото имаме обединение на транзитивни множества (доказателство - тук)
2. $\mathrm{EWO}(\cup x)$ - тъй като елементите на един ординал са ординали, то $\cup x$ е множество от ординали, и от доказаното по-горе $\mathrm{EWO}(\cup x)$.

Окончателно получихме $\mathrm{Ord}(\cup x)$.

Св11: $(\forall y \in x)\mathrm{Ord}(y) \Rightarrow \langle x, \in_x \rangle$ е добра наредба
Добре наредено множество е наредено множество, на което всяко непразно подмножество има най-малък елемент.
До сега сме доказали, че теоретико-множественото включване между ординали изпълнява следните свойства:

1. иррефлексивност - св1.1
2. асиметричност - св1.2
3. транзитивност - св2

Т.е от тук заключваме, че релацията $\in_x$ е релация на строга частична наредба. Нека $\varnothing \ne u \subseteq x$. От $\mathrm{EWO}(x) \Rightarrow \exists y(y \in u \And y \cap u = \varnothing)$. Нека $\alpha \in u$ е произволен елемент. Допускаме, че $\alpha < y \iff \alpha \in y$. Но от тук веднага $\alpha \in y \cap u$ - противоречие. Следователно $(\forall \alpha \in u)(y \le \alpha)$, с което показахме че всяко непразно подмножество има най-малък елемент.

Св12: $(\forall y \in x)\mathrm{Ord}(y) \Rightarrow (\cup x \le \beta \iff (\forall \alpha \in x)(\alpha \le \beta))$
Права посока: Нека $\alpha \in x$ е произволен елемент. Тогава $\alpha \subseteq \cup x = \beta \Rightarrow \alpha \le \beta$. Т.е $(\forall \alpha \in x )(\alpha \le \beta)$
Обратна посока: Нека $(\forall \alpha \in x)(\alpha \le \beta)$. Тогава $(\forall \alpha \in x)(\alpha \subseteq \beta) \Rightarrow \cup x \subseteq \beta \Rightarrow \cup x \le \beta$

Footnotes

1. $\in_x$ е индуцирана бинарна релация от теоретико множествено включване, върху множеството $x$