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<b\land b<c\Rightarrow a<c}
  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

.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s