Ordinal

Ordinals are an extension of the natural numbers. Ordinals can be used to describe the order type of a set. The order type of the natural numbers is the first infinite ordinal, $\omega$ . Ordinals can be added and multiplied. The sum of two ordinals $a$ and $b$ is the ordinal that describes the order type of a set with order type a concatenated with one of order type b. Warning! Ordinal addition is not commutative. For example $1+\omega=\omega$ , while $\omega+1>\omega$ .

Every ordinal characterizes the order type of the ordered ordinals less than it. For example, $0,1,2,\dotsb,\omega$ has order type $\omega+1$ .

The smallest ordinal that can't be constructed from $\omega$ by addition, multiplication, and exponentiation is $\varepsilon_0$ , the first fixed point of the map $\alpha\mapsto\omega^\alpha$ .

The Veblen $\phi$ functions

Based on the definition of $\varepsilon_0$ , Oswald Veblen in 1908 introduced an ordinal-indexed hierarchy of functions. $\phi_0(n)=\omega^n$ and $\phi_k$ enumerates the common fixed points of $\phi_m$ for all $m<k$ . $\phi_1(0)=\varepsilon_0$ , $\phi_2(0)$ is the smallest ordinal inaccessible from the $\varepsilon$ ordinals. It is called $\zeta_0$ . The set of all ordinals accessible from the $\phi$ functions, addition, multiplication, and exponentiation is well-ordered. It has order type $\Gamma_0$ , the Feferman–Schütte ordinal. It is the first fixed point of the map $\alpha\mapsto\phi_\alpha(0)$ .

Ordinal collapsing functions

Ordinal collapsing functions, or OCFs, "collapse" uncountable ordinals to give large countable ordinals. One example is a simplified version of Buchholz's OCF.

First, let $\Omega$ stand for the first uncountable ordinal, though it can be any ordinal which is of the form $\varepsilon_k$ and is greater than all the ordinals we can construct, for example the Church-Kleene ordinal $\omega_1^{CK}$ . Then we define $\psi(\alpha)$ as the smallest ordinal that cannot be expressed from $\{0,1,\omega,\Omega\}$ and using addition, multiplication, exponentiation, and applying the $\psi$ function to ordinals less than $\alpha$ .

Examples

Let's calculate $\psi(0)$ . We can get ordinals like $1,5,\omega,\omega^2+1,\omega^\omega,\omega^{\omega^\omega},\dotsb$ . We can also get uncountable ordinals such as $\Omega^\Omega,\Omega\omega,\Omega^\omega,\dotsb$ . The smallest ordinal we can't get is $\varepsilon_0$ . Therefore $\psi(0)=\varepsilon_0$ . $\psi(\alpha)=\varepsilon_\alpha$ holds until the first fixed point of $\alpha\mapsto\varepsilon_\alpha$ , which is $\zeta_0$ .

The function $\psi$ is "stuck" at $\zeta_0$ for all ordinals $\zeta_0\le o\le\Omega$ because $\zeta_0$ can't be constructed from smaller ordinals and $\psi$ . However, since $\psi(\Omega)=\zeta_0$ , for $\psi(\Omega+1)$ we can get $\zeta_0$ by using $\psi(\Omega)=\zeta_0$ . Then $\psi(\Omega+1)=\varepsilon_{\zeta_0+1}$ .

Some large notable ordinals are:

The Feferman–Schütte ordinal $\psi(\Omega^\Omega)$
The Ackermann ordinal $\psi(\Omega^{\Omega^2})$
The small Veblen ordinal $\psi(\Omega^{\Omega^\omega})$
The large Veblen ordinal $\psi(\Omega^{\Omega^\Omega})$

The limit of $\psi(\Omega),\psi(\Omega^\Omega),\psi(\Omega^{\Omega^\Omega}),\dotsb$ is $\psi(\varepsilon_{\Omega+1})$ the Bachmann-Howard ordinal, after it $\psi$ is constant.

Ordinal analysis

In modern mathematics, ordinals have been used to measure the strengths of various system. For example the ordinal strength of Peano arithmetic is $\varepsilon_0$ , which makes it one of the weakest systems studied in mathematics! Kripke–Platek set theory, a weakened form of Zermelo-Fraenkel set-theory, has ordinal strength equal to the Bachmann-Howard ordinal. Zermelo-Fraenkel set theory itself has an unknown ordinal strength.

Ordinal strengths can be used to show that certain statements are unprovable in certain systems. For example, the Kirby-Paris hydra theorems requires induction on the Bachmann-Howard ordinal, which means it is unprovable in Kripke-Platek set theory and Peano arithmetic. As another example, consider Gabriel Nivasch's fusible numbers $\mathcal{F}$ , defined by $0\in\mathcal{F}$ and if $x\in\mathcal{F}$ and $y\in\mathcal{F}$ then $\frac{x+y+1}{2}\in\mathcal{F}$ . Since $\mathcal{F}$ has order type $\varepsilon_0$ , statements like "For every $x\in\mathcal{F}$ there is a unique smallest $y>x$ and $y\in\mathcal{F}$ ."