Ordinal

Ordinals

The set $\alpha$ is an ordinal if $\alpha$ is a transitive set, that is $\forall z\forall y(z\in y\in x⟹z\in x),$ and $\in$ is a well-ordering of $\alpha$.

So for ordinals, the well-ordering $<$ is just the membership relation ∈, and every ordinal is the set of previous ordinals. For any two ordinals $\alpha$ and $\beta$, $\alpha <\beta ⟺\alpha \in \beta ⟺\alpha ⊊\beta$.

Types of Ordinals

Every ordinal $\alpha$ is one of the three following types:

• the initial ordinal, $\alpha =0$,
• a successor ordinal, $\alpha =\beta +1$ for some ordinal $\beta$,
• a limit ordinal if $\alpha$ is neither of the above.

Example: $0,1,2,3,\dots ,\omega ,\omega +1,\dots \omega \cdot 2,\dots {\omega }^2,\dots$ $0\leftrightarrow \varnothing$, $1\leftrightarrow \{0\}$, $\dots$ $\omega \leftrightarrow \{0,1,2,\dots \}$ And in this case we get all set countable.

Class of all Ordinals

This collection/class is too large to be a set. It is usually denoted by $On$. Informally, if there were a set of all ordinals then that set would itself be an ordinal, and we could get an even larger ordinal by taking its successor. But that gives a contradiction, since an ordinal cannot be isomorphic to a proper initial segment of itself. This is the Burali-Forti Paradox. Informally, like the Russell paradox, it shows that a collection described by a property may lead to a collection too large to be a set. There’s an axiom for set guaranteed the existence of $\omega$

Transfinite Induction

Let $P(\beta )$ be a statement about ordinals $\beta$ and let $\alpha$ be a fixed ordinal. Suppose for all $\beta <\alpha$ (for all $\beta \in On$),$[(\forall \gamma <\beta )P(\gamma )]⟹P(\beta ).$ Then $P(\beta )$ for all $\beta <\alpha$ (for all $\beta \in On$).

Remark

This can be think as more generalized version of normal induction, as it can be applied to “uncountable” cases.

Applications

In applications it is common to split the proof of the hypothesis $[(\forall \gamma <\beta )P(\gamma )]⟹P(\beta ).$ into three cases:

1. Prove $P(0).$
2. If $\beta =\gamma +1$ is a successor ordinal, prove $P(\beta )$ from the assumption $P(\gamma )$ is true.
3. If $\beta$ is a limit ordinal, prove $P(\beta )$ from the assumption $P(\gamma )$ is true for every $\gamma <\beta .$

Transfinite Sequence

A transfinite sequence is a function f whose domain is either an ordinal α or the class On of all ordinals. A transfinite sequence is usually denoted by ⟨aξ : ξ < α⟩ or ⟨aξ : ξ ∈ On⟩, where f(ξ) = aξ.

Well-ordering Principle (Axiom of Choice assumed)

Every set $X$ can be well-ordered.

Proof Let $f$ be a choice function for the nonempty subsets of $X.$ Define a transfinite sequence by $a_0=f(X),a_{\beta }=f\left(X\setminus \{a_{\xi }\mid \xi <\beta \}\right)$ if $X\setminus \{a_{\xi }\mid \xi <\beta \}$ is nonempty. Let $\theta$ be the first (and only by the construction) ordinal such that $\{a_{\beta }\mid \beta <\theta \}=X$. If not then we’ll get a contradiction, for example when $X$ countable, we would hit first uncountable ordinal and get contradiction with respect to cardinality. There is such a $\theta$, since otherwise there would be a one-one mapping from the class $On$ of all ordinals into the set $X$. But this would imply $On$ is a set , which is not the case. The required well-ordering is given by $a_{\xi }<a_{\beta }⟺\xi <\beta$

Theorem

The well-ordering principle is actually equivalent to Axiom of Choice. Suppose well-ordering principal we get the following statement for Axiom of Choice. Suppose the sets $A_i$ are all nonempty for $i\in I$. Then there exists a function f such that for all $i\in I,f(i)\in A_i$.