Ordinal Number

Ordinal number is a “order-type” of sets which is used to represent the “length” or “size” of well-ordering sets like $0 = \emptyset$, $1 = \{ \emptyset \}$. It’s also an extension to $\mathbb{N}$ since all of the natural number could be respresented by ordinal and it’s a proper superset as $\omega = \mathbb{N}$ and $\omega + 1 \neq \omega$ where $\alpha + 1 = \alpha \cup \{ \alpha \}$ called successor of $\alpha$.

The following is a useful theorem to classify the well-ordering set by ordinal number,

Theorem. Every well-ordering set is isomorphic to an ordinal number.

With AC(Axiom of Choice), we could show that every set could be well-ordering by some order. However, this theorem is equivalent to AC and not provable without any other equivalent axioms.

Transfinite induction is a generalization of normal mathematical induction on $\mathbb{N}$ to all ordinal numbers which states as follows,

Transfinite Induction. If we could prove the following,

1. $P(0)$ holds.
2. If $P(\alpha)$ holds, then $P(\alpha + 1)$ holds.
3. If $\alpha$ is a nonzero limit ordinal number, and for all $P(\beta)$ holds where $\beta < \alpha$, then $P(\alpha)$ holds.

Then, $P(\alpha)$ holds for all ordinal number $\alpha$.

Notice 3., the only different thing from usual mathematical induction is we have to deal with the case of limit ordinal number which defined as $\alpha \neq \beta + 1$ for all ordinal $\beta$.

We could define arithmetic on this, but however, there is something different. First, we have to deal with the limit ordinal by sequence. Second, the operation of addition, multiplication and exponentiation are not commutative.

Let me introduce the notion of sequence of ordinal first. The usual sequences  are defined on $\mathbb{N}$ (or $\omega$) if it’s infinite or on $\mathbb{Z}_{n}$ if it’s finite of length $n$. A transfinite sequence is a function defined on $\{ \eta : \eta < \alpha \}$. for some ordinal $\alpha$ or just $\{ a_{\eta} : \eta < \alpha \}$. Sometimes, we could call a function defined on all ordinal number just “sequence”.

Then, we shall introduce the notion of limit of the sequence. $\lim_{\eta \rightarrow \alpha} = \sup{} \{\gamma_{\eta} : \eta < \alpha\}$ where $\gamma_{\eta}$ is a non-decreasing sequence, $\alpha$ is some ordinal, and $\sup$ is the least upper bound of this well-ording set (that is, the existence of $\sup$ comes from it).

Now, we could define ordinal arithmetic as follows (by transfinite recursion).

Definition (Addition). For all ordinal numbers $\alpha$

1. $\alpha + 0 = \alpha$
2. $\alpha + (\beta + 1) = (\alpha + \beta) + 1$ for all $\beta$.
3. $\alpha + \beta = \lim_{\eta \rightarrow \beta} (\alpha + \eta)$ for all limit ordinal $\beta > 0$.

Definition (Multiplication).

1. $\alpha \cdot 0 = 0$
2. $\alpha \cdot (\beta + 1) = (\alpha \cdot \beta) + \alpha$
3. $\alpha \cdot \beta = \lim_{\eta \rightarrow \beta} \alpha \cdot \eta$ for all limit ordinal $\beta$

Definition (Exponentiation).

1. $\alpha^{0} = 1$
2. $\alpha^{\beta + 1} = \alpha^{\beta} \cdot \alpha$ for all $\beta$
3. $\alpha^{\beta} = \lim_{\eta \rightarrow \beta} \alpha^{\eta}$ for all limit $\beta > 0$

By the above definition, there is a theorem called Cantor Normal Form which states that every ordinal number has one unique representation as a finite sum of $\omega^{\beta}\cdot{}c$ where $\beta$ is an ordinal, and $c$ is a natural number. The concept of transfinite recusion could be apply to another generalization of well-ordering, the well-founded relation. Maybe it’s the next topic.