# Ordinal notations

Ordinals are important things in googology. Most of them are infinite, so they’re not just numbers. But we can use them to present some “levels”. Here I bring 4 ordinal notations I would use in this site – Cantor’s normal form, binary φ function, θ function, and Taranovsky’s notation.

# Definition of ordinals

Ordinals are something that fits these properties. First we need a binary relation “<” – that’s “less than” – on ordinals.

1. Any ordinal a and b must be and only be one of those 3 relations: a < b, a = b, or b < a.
2. a = a – that means a < a is always false.
3. ${a
4. Any sets or classes of ordinals must have a minimum.

We also write a < b as b > a. And ${a\leq b}$ means a < b or a = b.

# Basic notations

Here’s a very basic notation. The minimum of all ordinals is 0, and ${min\{\beta|\beta>\alpha\}=\alpha+1}$ is the successor of ${\alpha}$.

We call an ordinal x successor ordinal iff it’s the successor of some ordinal. x is a limit ordinal iff it’s neither 0 nor successor ordinal. We call the least limit ordinal ω – it’s the supremum of all natural numbers.

Then there’re some arithmetic on ordinals. First is the addition.

• ${\alpha+0=\alpha}$
• ${\alpha+(\beta+1)=(\alpha+\beta)+1}$
• ${\alpha+\beta=sup\{\alpha+\gamma|\gamma<\beta\}}$ for limit ordinal β

Then multiplication.

• ${\alpha0=0}$
• ${\alpha(\beta+1)=\alpha\beta+\alpha}$
• ${\alpha\beta=sup\{\alpha\gamma|\gamma<\beta\}}$ for limit ordinal β

Then exponentiation.

• ${\alpha^0=1}$
• ${\alpha^{\beta+1}=\alpha^\beta\alpha}$
• ${\alpha^\beta=sup\{\alpha^\gamma|\gamma<\beta\}}$ for limit ordinal β

Then ordinals have such properties:

1. ${\alpha+(\beta+\gamma)=(\alpha+\beta)+\gamma}$
2. ${\alpha(\beta\gamma)=(\alpha\beta)\gamma}$
3. ${\alpha(\beta+\gamma)=\alpha\beta+\alpha\gamma}$
4. ${\alpha^{\beta+\gamma}=\alpha^\beta\alpha^\gamma}$
5. ${\alpha^{\beta\gamma}=(\alpha^\beta)^\gamma}$

Finally, we have a notation called Cantor’s normal form.

• Ordinal ${\alpha\leq\omega}$ is in Cantor’s normal form.
• Ordinal ${\alpha=\omega^{\beta_1}k_1+\omega^{\beta_2}k_2+\cdots+\omega^{\beta_n}k_n}$ where n and all ki‘s are positive integers and ${\beta_1>\beta_2>\cdots>\beta_n}$ are all in Cantor’s normal form is in Cantor’s normal form.

If we just use Cantor’s normal form built from 0, 1 and ω, we have such a limit – ${\omega^{\omega^{\omega^{\cdots}}}=\varepsilon_0}$.

# Binary φ function

Binary φ function is defined as follows:

• ${\varphi(0,\beta)=\omega^\beta}$
• ${\varphi(\alpha,\beta)=min\{\gamma |(\forall\delta<\alpha:\gamma=\varphi(\delta,\gamma))\land(\forall\delta<\beta:\gamma>\varphi(\alpha,\delta))\}}$

The second line means, ${\varphi(\alpha,\beta)}$ is the (1+β)-th common fixed point that ${\gamma\mapsto\varphi(\delta,\gamma)}$ for all δ < α.

Explanation

${\varphi(0,\beta)=\omega^\beta}$ – that’s just a simple Cantor’s normal form.

${\varepsilon_0=\varphi(1,0)}$ is the least ordinal such that ${\omega^{\varepsilon_0}=\varepsilon_0}$. We say it’s the first fixed point of ${\alpha\mapsto\omega^\alpha}$. The second fixed point is ${\varepsilon_1=\varphi(1,1)}$, the third is ${\varepsilon_2=\varphi(1,2)}$, and so on. The ω-th is ${\varepsilon_\omega=\varphi(1,\omega)}$.

There’re also some ordinals such that ${\alpha=\varepsilon_\alpha}$ – the fixed points of ${\alpha\mapsto\varphi(1,\alpha)}$. The first fixed point is ${\varphi(2,0)}$, the second is ${\varphi(2,1)}$, and so on.

${\alpha\mapsto\varphi(2,\alpha)}$ also has fixed points. They’re ${\varphi(3,\beta)}$.

Generally speaking, ${\varphi(\alpha+1,\beta)}$ is the (1+β)-th fixed point of ${\gamma\mapsto\varphi(\alpha,\gamma)}$. This works for successor ordinal α.

For limit case, such as ω, ${\varphi(\omega,\beta)}$ is a fixed point of ${\gamma\mapsto\varphi(0,\gamma)}$, also ${\gamma\mapsto\varphi(1,\gamma)}$, also ${\gamma\mapsto\varphi(2,\gamma)}$, also ${\gamma\mapsto\varphi(3,\gamma)}$, and so on. It’s the common fixed point of ${\gamma\mapsto\varphi(\delta,\gamma)}$ for all δ < ω, and it’s the (1+β)-th ordinal have such property. Notice that this “common fixed point” also works for successor case, so we get the definition.

Using 0, 1, ω, by addition and φ function, we have such a limit – it’s the first fixed point of ${\gamma\mapsto\varphi(\gamma,0)}$ – that’s ${\Gamma_0}$. Generally, we use ${\Gamma_\beta}$ to present the (1+β)-th fixed point of ${\gamma\mapsto\varphi(\gamma,0)}$.

Advertisements