User:JRSpriggs/Ordinal notation

Background

Here we assume that ${\displaystyle \omega <\Omega =\omega _{1}}$ and that ${\displaystyle \Omega }$ is a regular ordinal. From ordinal arithmetic and Veblen hierarchy#Finitely many variables, we infer that:

${\displaystyle \alpha <\Omega \implies \alpha +\Omega =\Omega }$

${\displaystyle 1\leq \alpha <\Omega \implies \alpha \cdot \Omega =\Omega }$

${\displaystyle 2\leq \alpha <\Omega \implies \alpha ^{\Omega }=\Omega }$ including ${\displaystyle \omega ^{\Omega }=\Omega }$

${\displaystyle \alpha <\Omega \implies \phi (\alpha ,\Omega )=\Omega }$ including ${\displaystyle \epsilon _{\Omega }=\phi (1,\Omega )=\Omega }$

${\displaystyle \alpha <\Omega \land \beta <\Omega \implies \phi (\alpha ,\beta ,\Omega )=\Omega }$ including ${\displaystyle \Gamma _{\Omega }=\phi (1,0,\Omega )=\Omega }$.

${\displaystyle \phi (\Omega ,0)=\phi (\Omega ,0,0)=\Omega }$

Definition

First we define an auxiliary function D which serves to protect against circular definitions of countable ordinals. D (α) is the largest countable ordinal used in a canonical expression for α in terms of Ω.

If D_n (α) is defined for some n < ω, then let D (α) = D_n (α). There are cases:

case 1

${\displaystyle \alpha <\Omega \implies D_{n}(\alpha )=\alpha }$;

case 2

${\displaystyle \Omega \leq \alpha \land \alpha =\Omega ^{\beta }\cdot \gamma \,+\,\delta \,\land 1\leq \beta <\alpha \land 1\leq \gamma <\Omega \land \delta <\Omega ^{\beta }\land D_{n}(\beta ){\text{ is defined }}\land D_{n}(\delta ){\text{ is defined }}\implies D_{n+1}(\alpha )=\max(D_{n}(\beta ),\gamma ,D_{n}(\delta )))}$;

case 3 using the transfinitary Veblen function

${\displaystyle \Omega <\alpha \land \alpha =\phi (s)\land \langle \beta ,\gamma \rangle \in s\land \beta \neq 0\land \forall \delta \forall \eta (\langle \delta ,\eta \rangle \in s\implies \delta <\alpha \land \eta <\alpha \land D_{n}(\delta ){\text{ is defined }}\land D_{n}(\eta ){\text{ is defined }})\implies D_{n+1}(\alpha )=\max\{D_{n}(\delta ),D_{n}(\eta ):\langle \delta ,\eta \rangle \in s\}}$.

Now, we can define Λ by

${\displaystyle \forall \beta \leq \alpha (D(\beta ){\text{ is defined }})\implies \Lambda (\alpha )=\inf\{\gamma :D(\alpha )<\gamma <\Omega \land \forall \beta <\alpha \,(\gamma \neq \Lambda (\beta ))\}}$

via transfinite recursion on α.

Notice that D does not depend on Λ. The condition ⟨ β, γ ⟩ ∈ s ∧ β ≠ 0 in the third case is needed to avoid overlap with the second case. Since the ordinals are well ordered, Λ (α) is an element of the set of which it is the infimum and thus has the properties of an element of that set.

Domain of D

To evaluate D (α), we only need to compute the value of D on a finite number of ordinals. Suppose to the contrary that there was an ordinal α in the domain of D for which the calculation of D (α) never halted. Then further suppose that α were the least such ordinal. If α < Ω, then we are in case 1 and the output is just α itself. For α ≥ Ω, try case 2 (as explained below), either the exponent β is < α or it is equal to α. If it is less, then β, γ, and δ are all less than α and so their D values can be calculated in finite time. So do them one after the other and return the largest result. If β = α, then α is an epsilon number and we are in case 3. Then α = φ (s) for some function s. s must have finitely many parts (nonzero values and the arguments at which they occur). If they are all less than α then we can calculate their D values and return the largest. If α lacks a preferred form, then it is the LUB (least upper bound of the domain of D), contradicting the supposition that it is in the domain. [logical gap -- what if α is presented as φ of another function?]

Given an ordinal β < Ω, there are only a countable number of ordinals α for which

${\displaystyle D(\alpha )<\beta .}$

We prove this by induction on n. If n = 0, then we must be in case 1, so: | { α : D₀(α) < β } | = | β | ≤ ℵ₀.

For n+1: | { α : D_n+1(α) < β } | ≤ ℵ₀ + ℵ₀³ + ∑_k<ω (ℵ₀²)^k = ℵ₀.

| { α : D(α) < β } | ≤ ∑_n<ω | { α : D_n(α) < β } | ≤ ∑_n<ω ℵ₀ = ℵ₀.

Since Λ depends on previous values of Λ which in turn depend on their correspond values of D, it is necessary to show that there are no holes in the domain of D. That is, to show whenever D (β) is defined and α < β, then D (α) is defined.

Case 1 is not a problem, because any ordinal less than a countable ordinal is also countable and all countable ordinals are included.

Case 2 covers uncountable ordinals which are powers of omega or sums of powers of omega excluding epsilon numbers. If all the epsilon numbers below the least upper bound (LUB) of the domain are in the domain, then one can prove any ordinal below the LUB is included also. Otherwise, suppose α were the smallest ordinal below LUB which is not in the domain of D. The smallest power of Ω greater than α cannot have an exponent which is a limit because then some smaller exponent would give a power in between them. So there is a β ≥ 1 such that Ω^β ≤ α < Ω^β+1. So Ω^β·1 ≤ α < Ω^β·Ω and thus there is a γ such that Ω^β·γ ≤ α < Ω^β·(γ+1) with 1 ≤ γ < Ω. So Ω^β·γ ≤ α < Ω^β·γ + Ω^β. So there must be a δ such that Ω^β·γ + δ = α and δ < Ω^β. Either β < α or α is an epsilon number. δ < Ω^β ≤ α. So by the minimality of α, we must have β, γ, and δ all in the domain of D. Take n to be the smallest natural number such that they all lie in D_n. Then D (α) is defined as the maximum of their Ds, contradicting our supposition that α was not in the domain. It remains to show that all the epsilon numbers below LUB are in the domain which is the task of case 3.

Case 3: Suppose x is the smallest ordinal not in the domain of D. By the above, we know that x is an epsilon number larger than Ω. We wish to show that x = LUB. Suppose to the contrary (for reductio ad absurdum) that there is something in the domain of D larger than x. Let y be the smallest such ordinal. Then the interval [x, y) is a hole in the domain of D. By the above, y is also an epsilon number. And y = φ (s) for some set s. The ordinals in s must all be in the domain of D and less than y. So they must also be less than x. If x = φ (t) > D_φ (t), then the ordinals in t would be in the domain so x would also, a contradiction. So suppose to the contrary that every t with x = φ (t) has x = D_φ (t), i.e. x is one of the ordinals in t and x is an epsilon number with no preferred form. One of the properties of such ordinals is that whenever D_φ (s) < x we must also have φ (s) < x, that is y < x, a contradiction! So x = LUB, i.e. there are no holes in the domain of D.

Domain of Λ

Here we prove that Λ (α) is, in fact, defined whenever D (α) is defined. This is its entire intended domain. We only need to verify that the set of countable ordinals greater than D(α) and not in the image of Λ restricted to α is non-empty. If there were an α for which the set was empty, suppose α were the least such ordinal. Suppose

${\displaystyle \rho _{0}=D(\alpha )+1<\Omega }$

${\displaystyle \rho _{n+1}=\max(\rho _{n}+1,\sup\{\Lambda (\beta )+1:D(\beta )<\rho _{n}\land \beta <\alpha \})<\Omega }$

${\displaystyle \rho _{\omega }=\sup\{\rho _{n}:n<\omega \}<\Omega }$,

then we can infer that

${\displaystyle \rho _{\omega }\in \{\gamma :D(\alpha )<\gamma <\Omega \land \forall \beta <\alpha \,(\gamma \neq \Lambda (\beta ))\},}$

because if

${\displaystyle \beta <\alpha \land \Lambda (\beta )=\rho _{\omega }}$

then

${\displaystyle D(\beta )<\rho _{\omega }}$

so for some n < ω,

${\displaystyle D(\beta )<\rho _{n}}$

${\displaystyle \Lambda (\beta )<\rho _{n+1}<\rho _{\omega }=\Lambda (\beta ),}$

a contradiction!

Ordering

First we show that Λ is an injective function from its domain to Ω. Suppose α ≠ β, then either α < β or β < α. If α < β, then

${\displaystyle \Lambda (\beta )\in \{\gamma :D(\beta )<\gamma <\Omega \land \forall \delta <\beta (\gamma \neq \Lambda (\delta ))\}}$

${\displaystyle D(\beta )<\Lambda (\beta )<\Omega \land \forall \delta <\beta (\Lambda (\beta )\neq \Lambda (\delta ))}$.

Taking δ to be α, we get

${\displaystyle \Lambda (\beta )\neq \Lambda (\alpha )}$.

Similarly if β < α.

Thus Λ is a kind of Ordinal collapsing function, but we choose injectivity over continuity.

To show that:

${\displaystyle \Lambda (\alpha )<\Lambda (\beta )\iff (\alpha <\beta \land D(\alpha )<\Lambda (\beta ))\lor (\beta <\alpha \land \Lambda (\alpha )\leq D(\beta ))}$.

Suppose α < β and D(α) < Λ(β). Since β ≮ α and Λ is injective

${\displaystyle D(\alpha )<\Lambda (\beta )<\Omega \land \forall \delta <\alpha (\Lambda (\beta )\neq \Lambda (\delta ))}$

${\displaystyle \Lambda (\beta )\in \{\gamma :D(\alpha )<\gamma <\Omega \land \forall \delta <\alpha (\gamma \neq \Lambda (\delta ))\}}$

${\displaystyle \Lambda (\alpha )\leq \Lambda (\beta )}$.

Using injectivity again

${\displaystyle \Lambda (\alpha )<\Lambda (\beta )}$.

Suppose β < α and Λ (α) ≤ D (β).

${\displaystyle \Lambda (\alpha )\leq D(\beta )<\Lambda (\beta )}$.

So again

${\displaystyle \Lambda (\alpha )<\Lambda (\beta )}$.

Thus the right hand side implies the left hand side.

Now suppose the left hand side is true. Since Λ is a single-valued function, we must have α ≠ β. Thus either α < β or β < α.

If α < β, then

${\displaystyle D(\alpha )<\Lambda (\alpha )<\Lambda (\beta )}$

${\displaystyle \alpha <\beta \land D(\alpha )<\Lambda (\beta )}$.

So the right hand side is true.

If β < α, then we must have Λ (α) ≤ D (β) because otherwise

${\displaystyle D(\beta )<\Lambda (\alpha )}$

${\displaystyle \beta <\alpha \land D(\beta )<\Lambda (\alpha )}$.

So using the first case of the RHS → LHS with α and β switched, we would get

${\displaystyle \Lambda (\beta )<\Lambda (\alpha )<\Lambda (\beta )}$

which is a contradiction. So the right hand side is true in both cases. Q.E.D.

Relationship to ξ notation

This system generalizes the ξ notation to a much stronger notation. For α, β < Ω,

${\displaystyle \xi (\alpha ,\beta )=\Lambda (\Omega \cdot \alpha \,+\,\beta ).}$

That is:

${\displaystyle \beta <\Omega \implies \Lambda (\beta )=\beta +1,}$

${\displaystyle \alpha <\Omega \land \beta <\Omega \land n<\omega \land (\omega \cdot \beta )<\omega ^{\omega ^{\alpha }}\cdot (\omega \cdot \beta )\implies \Lambda (\Omega \cdot (1+\alpha )+(\omega \cdot \beta )+n)=\omega ^{\omega ^{\alpha }}\cdot ((\omega \cdot \beta )+n),}$

${\displaystyle \alpha <\Omega \land \beta <\Omega \land (\alpha <\omega ^{\alpha }\lor 0<\beta )\land n<\omega \land (\omega \cdot \beta )=\omega ^{\omega ^{\alpha }}\cdot (\omega \cdot \beta )\implies \Lambda (\Omega \cdot (1+\alpha )+(\omega \cdot \beta )+n)=(\omega \cdot \beta )+\omega ^{\omega ^{\alpha }}\cdot (1+n),}$

${\displaystyle \alpha =\omega ^{\alpha }<\Omega \land n<\omega \implies \Lambda (\Omega \cdot \alpha +n)=\alpha \cdot (2+n).}$

Arithmetic

where

${\displaystyle 1=\xi (0,0).}$

${\displaystyle 2=\xi (0,1).}$

Addition:

${\displaystyle 0+\alpha =\alpha +0=\alpha .}$

${\displaystyle \alpha +\xi (0,\beta )=\alpha +\beta +1=\xi (0,\alpha +\beta ).}$

${\displaystyle \alpha <\gamma \implies \alpha +\xi (\gamma ,\delta )=\xi (\gamma ,\delta ).}$

${\displaystyle \alpha <\gamma \implies \xi (\alpha ,\beta )+\xi (\gamma ,\delta )=\beta +\xi (\gamma ,\delta ).}$

${\displaystyle \alpha =\gamma \land \gamma <\omega ^{\gamma }\implies \xi (\alpha ,\beta )+\xi (\gamma ,\delta )=\xi (\gamma ,\beta +1+\delta ).}$

${\displaystyle \alpha =\gamma \land \gamma =\omega ^{\gamma }\implies \xi (\alpha ,\beta )+\xi (\gamma ,\delta )=\xi (\gamma ,\beta +2+\delta ).}$

${\displaystyle \alpha =\gamma \land \gamma =\omega ^{\gamma }\implies \alpha +\xi (\gamma ,\delta )=\xi (\gamma ,1+\delta ).}$

${\displaystyle \alpha =\gamma \land \gamma =\omega ^{\gamma }\implies \xi (\alpha ,\beta )+\gamma =\xi (\gamma ,\xi (0,\beta )).}$

${\displaystyle \alpha >\gamma \land \gamma <\omega ^{\gamma }\implies \xi (\alpha ,\beta )+\xi (\gamma ,\delta )=\xi (\gamma ,\xi (\alpha ,\beta )+1+\delta ).}$

${\displaystyle \alpha >\gamma \land \gamma =\omega ^{\gamma }\implies \xi (\alpha ,\beta )+\xi (\gamma ,\delta )=\xi (\gamma ,\xi (\alpha ,\beta )+2+\delta ).}$

${\displaystyle \alpha =\omega ^{\alpha }>\gamma \land \gamma <\omega ^{\gamma }\implies \alpha +\xi (\gamma ,\delta )=\xi (\gamma ,\alpha +1+\delta ).}$

${\displaystyle \alpha =\omega ^{\alpha }>\gamma \land \gamma =\omega ^{\gamma }\implies \alpha +\xi (\gamma ,\delta )=\xi (\gamma ,\alpha +2+\delta ).}$

Multiplication:

${\displaystyle \alpha \cdot 0=0\cdot \alpha =0.}$

${\displaystyle \alpha \cdot 1=1\cdot \alpha =\alpha .}$

${\displaystyle \alpha \cdot \xi (0,\beta )=\alpha \cdot \beta +\alpha .}$

${\displaystyle \alpha \geq \gamma \geq 1\land 1\leq \beta \implies \xi (\alpha ,\beta )\cdot \xi (\gamma ,\delta )=\xi (\alpha ,\beta \cdot \xi (\gamma ,\delta )).}$

${\displaystyle \alpha \geq \gamma \geq 1\implies \xi (\alpha ,0)\cdot \xi (\gamma ,\delta )=\xi (\alpha ,\xi (\gamma ,\delta )).}$

${\displaystyle \alpha <\gamma \land 1\leq \beta \implies \xi (\alpha ,\beta )\cdot \xi (\gamma ,\delta )=\beta \cdot \xi (\gamma ,\delta ).}$

${\displaystyle \alpha <\gamma \implies \xi (\alpha ,0)\cdot \xi (\gamma ,\delta )=\xi (\gamma ,\delta ).}$

${\displaystyle \alpha \geq \gamma =\omega ^{\gamma }\land 1\leq \beta \implies \xi (\alpha ,\beta )\cdot \gamma =\xi (\alpha ,\beta \cdot \gamma ).}$

${\displaystyle \alpha \geq \gamma =\omega ^{\gamma }\implies \xi (\alpha ,0)\cdot \gamma =\xi (\alpha ,\gamma ).}$

${\displaystyle \alpha <\gamma =\omega ^{\gamma }\land 1\leq \beta \implies \xi (\alpha ,\beta )\cdot \gamma =\beta \cdot \gamma .}$

${\displaystyle \alpha <\gamma =\omega ^{\gamma }\implies \xi (\alpha ,0)\cdot \gamma =\gamma .}$

${\displaystyle \alpha =\omega ^{\alpha }\geq \gamma \geq 1\implies \alpha \cdot \xi (\gamma ,\delta )=\xi (\alpha ,\xi (\gamma ,\delta )).}$

${\displaystyle \alpha =\omega ^{\alpha }<\gamma \implies \alpha \cdot \xi (\gamma ,\delta )=\xi (\gamma ,\delta ).}$

Exponentiation:

${\displaystyle \alpha ^{0}=1.}$

${\displaystyle 0<\alpha \implies 0^{\alpha }=0.}$

${\displaystyle \alpha ^{1}=\alpha .}$

${\displaystyle 1^{\alpha }=1.}$

${\displaystyle \alpha ^{\xi (0,\beta )}=\alpha ^{\beta }\cdot \alpha .}$

tbd

Define the functions lo and hi by:

${\displaystyle \omega ^{\alpha }\leq 1+\beta <\omega ^{\alpha +1}\implies \operatorname {lo} (\beta )=\alpha .}$

${\displaystyle \operatorname {hi} (\alpha )=\omega ^{\alpha }\approx \xi (1+\operatorname {lo} (\alpha ),0)\approx \operatorname {lo} (\xi (1+\alpha ,0)).}$

Cases for exponentiation:

${\displaystyle 2\leq \alpha <\omega \implies \alpha ^{\xi (1,\delta )}=\operatorname {hi} (\delta ).}$

${\displaystyle 2\leq \alpha <\omega \implies \alpha ^{\xi (2+\gamma ,\delta )}=\operatorname {hi} (\xi (2+\gamma ,\delta )).}$

${\displaystyle {\xi (1+\alpha ,\beta )}^{\xi (1+\gamma ,\delta )}=\operatorname {hi} (\operatorname {lo} (\xi (1+\alpha ,\beta ))\cdot \xi (1+\gamma ,\delta )).}$

${\displaystyle \alpha =\omega ^{\alpha }\implies \alpha ^{\xi (1+\gamma ,\delta )}=\operatorname {hi} (\alpha \cdot \xi (1+\gamma ,\delta )).}$

${\displaystyle \xi (1+\alpha ,\beta )>\gamma =\omega ^{\gamma }\implies {\xi (1+\alpha ,\beta )}^{\gamma }=\operatorname {hi} (\operatorname {lo} (\xi (1+\alpha ,\beta ))\cdot \gamma ).}$

${\displaystyle 2\leq \alpha <\gamma =\omega ^{\gamma }\implies \alpha ^{\gamma }=\gamma .}$

To compute lo and hi, do:

${\displaystyle \operatorname {lo} (0)=0.}$

${\displaystyle \beta =\omega ^{\beta }\implies \operatorname {lo} (\beta )=\beta .}$

${\displaystyle \operatorname {lo} (\xi (0,\beta ))=\operatorname {lo} (\beta ).}$

${\displaystyle \operatorname {lo} (\xi (1+\alpha ,\beta ))=\operatorname {hi} (\alpha )+\operatorname {lo} (\beta ).}$

${\displaystyle \operatorname {hi} (0)=1.}$

${\displaystyle \beta =\omega ^{\beta }\implies \operatorname {hi} (\beta )=\beta .}$

${\displaystyle \operatorname {hi} (\xi (0,\beta ))=\operatorname {hi} (\beta )\cdot \xi (1,0).}$

${\displaystyle \operatorname {hi} (\xi (\alpha ,\beta ))=\operatorname {hi} (\xi (\alpha ,0)\cdot (1+\beta )).}$

Epsinums:

${\displaystyle \alpha =\omega ^{\alpha }\implies \alpha +\alpha =\alpha \cdot 2=\omega ^{\omega ^{\alpha }}\cdot 2=\xi (\alpha ,0).}$

${\displaystyle \alpha =\omega ^{\alpha }\implies \alpha \cdot \alpha =\alpha ^{2}=\omega ^{\omega ^{\alpha }}\cdot \alpha =\xi (\alpha ,\alpha ).}$

${\displaystyle \alpha =\omega ^{\alpha }\implies \alpha ^{\alpha }=\omega ^{\omega ^{\alpha }\cdot \omega ^{\alpha }}=\omega ^{\omega ^{\alpha +\alpha }}=\xi (\xi (\alpha ,0),0).}$

${\displaystyle \alpha =\omega ^{\alpha }<\beta =\omega ^{\beta }\implies \alpha +\beta =\alpha \cdot \beta =\alpha ^{\beta }=\beta .}$

${\displaystyle \alpha =\omega ^{\alpha }>\beta =\omega ^{\beta }\implies \alpha +\beta =\beta \cdot (\alpha +1)=\omega ^{\omega ^{\beta }}\cdot (\alpha +1)=\xi (\beta ,\alpha ).}$

${\displaystyle \alpha =\omega ^{\alpha }>\beta =\omega ^{\beta }\implies \alpha \cdot \beta =\omega ^{\omega ^{\alpha }}\cdot \beta =\xi (\alpha ,\beta ).}$

${\displaystyle \alpha =\omega ^{\alpha }>\beta =\omega ^{\beta }\implies \alpha ^{\beta }=\omega ^{\omega ^{\alpha }\cdot \omega ^{\beta }}=\omega ^{\omega ^{\alpha +\beta }}=\xi (\xi (\beta ,\alpha ),0).}$

tbd

Conversion formulas and lemmas:

${\displaystyle \alpha +1=\xi (0,\alpha ).}$

${\displaystyle 1\leq \gamma <\omega ^{\omega ^{\beta +1}}\land n<\omega \implies \omega ^{\omega ^{\beta +1}}\cdot \alpha +\omega ^{\omega ^{\beta }}\cdot (\omega \cdot \gamma +n)=\xi (1+\beta ,\omega ^{\omega ^{\beta +1}}\cdot \alpha +(\omega \cdot \gamma +n)).}$

${\displaystyle (0<\alpha \lor \beta <\omega ^{\beta })\land n<\omega \implies \omega ^{\omega ^{\beta +1}}\cdot \alpha +\omega ^{\omega ^{\beta }}\cdot (n+1)=\xi (1+\beta ,\omega ^{\omega ^{\beta +1}}\cdot \alpha +n).}$

${\displaystyle \beta =\omega ^{\beta }\land n<\omega \implies \omega ^{\omega ^{\beta }}\cdot (n+2)=\xi (\beta ,n).}$

${\displaystyle \beta +\gamma =\xi (1+\alpha ,\beta )\implies \gamma <\omega ^{\omega ^{\alpha +1}}.}$

Relationship to binary Veblen hierarchy

In general, this system is also related to the binary Veblen hierarchy by

${\displaystyle \Lambda (\Omega ^{2}\,+\,\Omega \cdot \alpha \,+\,\beta )=\phi (1+\alpha ,\beta +k)}$

where α, β < Ω and k is either 0 or 1.

More specifically, translating from φ to Λ:

${\displaystyle \alpha <\Omega \land \beta <\Omega \land n<\omega \land \max(1+\alpha ,\omega \cdot \beta )<\phi (1+\alpha ,\omega \cdot \beta )\implies \Lambda (\Omega ^{2}+\Omega \cdot \alpha +\omega \cdot \beta +n)=\phi (1+\alpha ,\omega \cdot \beta +n)}$.

${\displaystyle \alpha <\Omega \land \beta <\Omega \land n<\omega \land \max(1+\alpha ,\omega \cdot \beta )=\phi (1+\alpha ,\omega \cdot \beta )\implies \Lambda (\Omega ^{2}+\Omega \cdot \alpha +\omega \cdot \beta +n)=\phi (1+\alpha ,\omega \cdot \beta +1+n)}$.

Translating from Λ to φ:

${\displaystyle \phi (0,\beta )=\omega ^{\beta }}$.

${\displaystyle \alpha <\Omega \land \beta <\Omega \land n<\omega \land \sup\{\Lambda (\Omega ^{2}+\Omega \cdot \alpha +\gamma ):\gamma <(\omega \cdot \beta )\}=\Lambda (\Omega ^{2}+\Omega \cdot \alpha +(\omega \cdot \beta ))\implies \phi (1+\alpha ,\omega \cdot \beta +n)=\Lambda (\Omega ^{2}+\Omega \cdot \alpha +\omega \cdot \beta +n)}$.

${\displaystyle \alpha <\Omega \land 0<\beta <\Omega \land n<\omega \land \sup\{\Lambda (\Omega ^{2}+\Omega \cdot \alpha +\gamma ):\gamma <(\omega \cdot \beta )\}<\Lambda (\Omega ^{2}+\Omega \cdot \alpha +(\omega \cdot \beta ))\implies \phi (1+\alpha ,\omega \cdot \beta +1+n)=\Lambda (\Omega ^{2}+\Omega \cdot \alpha +\omega \cdot \beta +n)\land }$

${\displaystyle \phi (1+\alpha ,\omega \cdot \beta )=\sup\{\Lambda (\Omega ^{2}+\Omega \cdot \alpha +\gamma ):\gamma <(\omega \cdot \beta )\}}$.

${\displaystyle \alpha <\Omega \land n<\omega \land \sup\{\Lambda (\Omega ^{2}+\Omega \cdot \gamma ):\gamma <(\omega \cdot \alpha )\}<\Lambda (\Omega ^{2}+\Omega \cdot (\omega \cdot \alpha ))\implies \phi (1+(\omega \cdot \alpha ),1+n)=\Lambda (\Omega ^{2}+\Omega \cdot (\omega \cdot \alpha )+n)\land }$

${\displaystyle \phi (1+(\omega \cdot \alpha ),0)=\sup\{\Lambda (\Omega ^{2}+\Omega \cdot \gamma ):\gamma <(\omega \cdot \alpha )\}}$.

Translating from Γ to Λ :

${\displaystyle \alpha =\Gamma _{\alpha }<\Omega \land n<\omega \implies \omega \cdot \alpha =\alpha \land \Lambda (\Omega ^{2}\cdot 2+\alpha +n)=\Gamma _{\alpha +1+n}}$

${\displaystyle \omega \cdot \alpha <\Gamma _{\omega \cdot \alpha }<\Omega \land n<\omega \implies \Lambda (\Omega ^{2}\cdot 2+\omega \cdot \alpha +n)=\Gamma _{\omega \cdot \alpha +n}}$

Translating from Λ to Γ :

${\displaystyle n<\omega \implies \Gamma _{n}=\Lambda (\Omega ^{2}\cdot 2+n)}$.

${\displaystyle 0<\alpha <\Omega \land n<\omega \land \sup\{\Lambda (\Omega ^{2}\cdot 2+\beta )\,:\,\beta <\omega \cdot \alpha \}=\Lambda (\Omega ^{2}\cdot 2+\omega \cdot \alpha )\implies \Gamma _{\omega \cdot \alpha +n}=\Lambda (\Omega ^{2}\cdot 2+\omega \cdot \alpha +n)}$.

${\displaystyle 0<\alpha <\Omega \land n<\omega \land \sup\{\Lambda (\Omega ^{2}\cdot 2+\beta )\,:\,\beta <\omega \cdot \alpha \}<\Lambda (\Omega ^{2}\cdot 2+\omega \cdot \alpha )\implies \Gamma _{\omega \cdot \alpha +1+n}=\Lambda (\Omega ^{2}\cdot 2+\omega \cdot \alpha +n)\land \Gamma _{\omega \cdot \alpha }=\sup\{\Lambda (\Omega ^{2}\cdot 2+\beta )\,:\,\beta <\omega \cdot \alpha \}}$.

Important ordinals

Identifying important ordinals with Λ:

• First infinite ordinal ${\displaystyle \omega =\Lambda (\Omega )}$
• First epsilon number ${\displaystyle \epsilon _{0}=\Lambda (\Omega ^{2})}$
• Feferman–Schütte ordinal ${\displaystyle \Gamma _{0}=\Lambda (\Omega ^{2}\cdot 2)}$
• Small Veblen ordinal ${\displaystyle \Lambda (\Omega ^{\omega })}$
• Large Veblen ordinal ${\displaystyle \Lambda (\Omega ^{\Omega })}$
• Bachmann–Howard ordinal ${\displaystyle \Lambda (\epsilon _{\Omega +1})}$

I have not read a description of Ackermann's ordinal notations from a reliable source, so this is just a guess based on the information available in Wikipedia. The Ackermann ordinal is probably Λ (Ω⁴).

I do not know about Buchholz's ordinal or the Takeuti–Feferman–Buchholz ordinal.

Relationship to finitary Veblen hierarchy

In what follows, α, β, γ are less than Ω and j, k, m, n are less than ω.

${\displaystyle \Lambda (\Omega ^{2}\cdot (1+\alpha )+\Omega \cdot \beta +\gamma )=\phi (\alpha ,\,\beta +j,\,\gamma +k)}$

where k is usually 0, but sometimes 1 when necessary to skip over values which would otherwise be fixed points; j is 1, if α=0 and β<ω, otherwise it is 0 because Λ handles mere powers of ω differently.

If m is at least 3 and α_m≠0, then

${\displaystyle \Lambda (\Omega ^{m}\cdot \alpha _{m}+\Omega ^{m-1}\cdot \alpha _{m-1}+...+\Omega \cdot \alpha _{1}+\alpha _{0})=\phi (\alpha _{m},\,\alpha _{m-1},\,...\alpha _{1},\,\alpha _{0}+k)}$.

Specifically, translating from φ to Λ :

${\displaystyle \max(\alpha _{m},\ldots ,\alpha _{1},(\omega \cdot \beta ))<\phi (\alpha _{m},\,\alpha _{m-1},\,...\alpha _{1},\,(\omega \cdot \beta ))\implies \Lambda (\Omega ^{m}\cdot \alpha _{m}+\Omega ^{m-1}\cdot \alpha _{m-1}+...+\Omega \cdot \alpha _{1}+(\omega \cdot \beta )+n)=\phi (\alpha _{m},\,\alpha _{m-1},\,...\alpha _{1},\,(\omega \cdot \beta )+n)}$.

${\displaystyle \max(\alpha _{m},\ldots ,\alpha _{1},(\omega \cdot \beta ))=\phi (\alpha _{m},\,\alpha _{m-1},\,...\alpha _{1},\,(\omega \cdot \beta ))\implies \Lambda (\Omega ^{m}\cdot \alpha _{m}+\Omega ^{m-1}\cdot \alpha _{m-1}+...+\Omega \cdot \alpha _{1}+(\omega \cdot \beta )+n)=\phi (\alpha _{m},\,\alpha _{m-1},\,...\alpha _{1},\,(\omega \cdot \beta )+1+n)}$.

Translating from Λ to φ :

${\displaystyle \sup\{\Lambda (\Omega ^{m}\cdot \alpha _{m}+\Omega ^{m-1}\cdot \alpha _{m-1}+...+\Omega \cdot \alpha _{1}+\gamma )\,:\,\gamma <(\omega \cdot \beta )\}=\Lambda (\Omega ^{m}\cdot \alpha _{m}+\Omega ^{m-1}\cdot \alpha _{m-1}+...+\Omega \cdot \alpha _{1}+(\omega \cdot \beta ))\implies }$

${\displaystyle \phi (\alpha _{m},\,\alpha _{m-1},\,...\alpha _{1},\,(\omega \cdot \beta )+n)=\Lambda (\Omega ^{m}\cdot \alpha _{m}+\Omega ^{m-1}\cdot \alpha _{m-1}+...+\Omega \cdot \alpha _{1}+(\omega \cdot \beta )+n)}$.

${\displaystyle \sup\{\Lambda (\Omega ^{m}\cdot \alpha _{m}+\Omega ^{m-1}\cdot \alpha _{m-1}+...+\Omega \cdot \alpha _{1}+\gamma )\,:\,\gamma <(\omega \cdot \beta )\}<\Lambda (\Omega ^{m}\cdot \alpha _{m}+\Omega ^{m-1}\cdot \alpha _{m-1}+...+\Omega \cdot \alpha _{1}+(\omega \cdot \beta ))\implies }$

${\displaystyle \phi (\alpha _{m},\,\alpha _{m-1},\,...\alpha _{1},\,(\omega \cdot \beta )+1+n)=\Lambda (\Omega ^{m}\cdot \alpha _{m}+\Omega ^{m-1}\cdot \alpha _{m-1}+...+\Omega \cdot \alpha _{1}+(\omega \cdot \beta )+n)\land }$

${\displaystyle \phi (\alpha _{m},\,\alpha _{m-1},\,...\alpha _{1},\,(\omega \cdot \beta ))=\sup\{\Lambda (\Omega ^{m}\cdot \alpha _{m}+\Omega ^{m-1}\cdot \alpha _{m-1}+...+\Omega \cdot \alpha _{1}+\gamma )\,:\,\gamma <(\omega \cdot \beta )\}}$.

For example,

${\displaystyle \Lambda (\Omega ^{4}\cdot 3)=\phi (3,0,0,0,0).}$

The finitary Veblen function is related to the transfinitary Veblen function as follows for m < ω:

${\displaystyle \phi (\alpha _{m},\,\alpha _{m-1},\,...\alpha _{1},\,\alpha _{0})=\phi (\{\langle j,\alpha _{j}\rangle :j\leq m\land \alpha _{j}\neq 0\})}$.

The small Veblen ordinal (SVO) is:

${\displaystyle SVO=\phi (\{\langle \omega ,1\rangle \})=\Lambda (\Omega ^{\omega })}$.

${\displaystyle s<\{\langle \omega ,1\rangle \}\land D_{\phi }(s)<SVO\,\implies \,\phi (s)<SVO}$.

Relationship to transfinitary Veblen hierarchy

If Ω²·ω ≤ α < Ω^Ω and

${\displaystyle \alpha =\Omega ^{\beta _{1}}\cdot \gamma _{1}+\ldots +\Omega ^{\beta _{n}}\cdot \gamma _{n}+\omega \cdot \delta }$

with

${\displaystyle \beta _{1}>\ldots >\beta _{n}>0\land 0<\gamma _{1}<\Omega \land \ldots \land 0<\gamma _{n}<\Omega \land \delta <\Omega }$

${\displaystyle s=\{\langle \beta _{j},\gamma _{j}\rangle :1\leq j\leq n\}\cup \{\langle 0,\omega \cdot \delta \rangle$ :\delta \neq 0\}}

and m < ω, then

${\displaystyle D_{\phi }(s)<\phi (s)\implies \Lambda (\alpha +m)=\phi (\{\langle \beta _{j},\gamma _{j}\rangle :1\leq j\leq n\}\cup \{\langle 0,\omega \cdot \delta +m\rangle$ :\omega \cdot \delta +m\neq 0\})}

and

${\displaystyle D_{\phi }(s)=\phi (s)\implies \Lambda (\alpha +m)=\phi (\{\langle \beta _{j},\gamma _{j}\rangle :1\leq j\leq n\}\cup \{\langle 0,\omega \cdot \delta +1+m\rangle \}).}$

For α < Ω^Ω, the values of Λ (α) will either be non-epsilon numbers or epsilon numbers with a preferred form. For Ω^Ω ≤ α, the values of Λ (α) will be epsilon numbers lacking a preferred form. In this case, there is no useful equivalent expression in the transfinitary Veblen scheme.

Image of Λ

As we know, 0 is not in the image of Λ, but 1 = Λ(0); 2 = Λ(1); etc.. We will now characterize the countable ordinals not in the image of Λ. Suppose ν is a countable ordinal not in the image of Λ. Let

${\displaystyle \eta _{0}=\Omega +1,}$

${\displaystyle \eta _{n+1}=\phi (\{\langle \eta _{n},\eta _{n}\rangle ,\langle 0,\eta _{n}\rangle \}).}$

Notice that ${\displaystyle \sup\{\eta _{n}:n<\omega \}}$ is the least upper bound of the domain of D.

Also ${\displaystyle n<\omega \implies D(\eta _{n})=1.}$

Let

${\displaystyle \rho _{n}=\Lambda (\eta _{n}+\nu )}$

${\displaystyle \rho _{\omega }=\sup\{\rho _{n}:n<\omega \}.}$

Then ρ_ω will be the next ordinal after ν which not in the image of Λ.

If ν+1 = Λ(ν) ≤ μ < ρ_ω, then μ is in the image of Λ. For suppose otherwise, then for some n

${\displaystyle D(\eta _{n}+\nu )=\max(\nu ,1)\leq \mu <\rho _{n}}$

so μ belongs to the set in the definition of ρ_n and thus

${\displaystyle \rho _{n}=\Lambda (\eta _{n}+\nu )<\mu <\rho _{n}}$

a contradiction! Thus every ordinal strictly between ν and ρ_ω is in the image of Λ.

If ρ_ω were in the image of Λ, then for some α

${\displaystyle \Lambda (\alpha )=\rho _{\omega }}$

${\displaystyle D(\alpha )<\rho _{\omega },}$

so for some n < ω,

${\displaystyle D(\alpha )<\rho _{n}\land \alpha <\eta _{n}\leq \eta _{n}+\nu }$

Remember ${\displaystyle \rho _{n}=\Lambda (\eta _{n}+\nu )}$ and ${\displaystyle \alpha <\eta _{n}+\nu \land D(\alpha )<\Lambda (\eta _{n}+\nu )\implies \Lambda (\alpha )<\Lambda (\eta _{n}+\nu )}$. So

${\displaystyle \Lambda (\alpha )<\rho _{n}<\rho _{\omega }=\Lambda (\alpha ),}$

a contradiction! So ρ_ω is not in the image of Λ.

Any limits of ordinals not in the image are also not in the image. Suppose to the contrary that there were an ordinal π which was in image despite being a limit of ordinals not in the image. Then for some α :

${\displaystyle D(\alpha )<\Lambda (\alpha )=\pi <\Omega }$

and there were an ordinal ν not in the image such that

${\displaystyle D(\alpha )<\nu <\pi }$

${\displaystyle D(\alpha )<\nu <\Omega \land \forall \delta <\alpha (\nu \neq \Lambda (\delta ))}$

${\displaystyle \nu \in \{\gamma :D(\alpha )<\gamma <\Omega \land \forall \delta <\alpha (\gamma \neq \Lambda (\delta ))\}}$

${\displaystyle \Lambda (\alpha )\leq \nu }$

${\displaystyle \pi \leq \nu <\pi }$

which is a contradiction. So π must not be in the image.

Fundamental sequences for Λ

Define the complexity, X, of some ordinals (number of "Λ"s appearing in its canonical expression) by

${\displaystyle X(0)=0}$

${\displaystyle X(\alpha ){\text{ is defined }}\implies X(\Lambda (\alpha ))=X(\alpha )+1}$

${\displaystyle \Omega \leq \alpha \land \alpha =\Omega ^{\beta }\cdot \gamma \,+\,\delta \,\land 1\leq \beta <\alpha \land 1\leq \gamma <\Omega \land \delta <\Omega ^{\beta }\land X(\beta ){\text{ is defined }}\land X(\gamma ){\text{ is defined }}\land X(\delta ){\text{ is defined }}\implies X(\alpha )=X(\beta )+X(\gamma )+X(\delta )}$

${\displaystyle \Omega <\alpha \land \alpha =\phi (s)\land \langle \beta ,\gamma \rangle \in s\land \beta \neq 0\land \forall \delta \forall \eta (\langle \delta ,\eta \rangle \in s\implies \delta <\alpha \land \eta <\alpha \land X(\delta ){\text{ is defined }}\land X(\eta ){\text{ is defined }})\implies X(\alpha )=\Sigma \{X(\delta )+X(\eta ):\langle \delta ,\eta \rangle \in s\}.}$

Notice

${\displaystyle X(\alpha ){\text{ is defined }}\implies X(\alpha )<\omega }$

${\displaystyle X(D(\alpha ))<X(\Lambda (\alpha )).}$

There is a countable ordinal ν₁ (the least nonzero ordinal which is not in the image of Λ) such that

${\displaystyle X(\alpha ){\text{ is defined }}\iff D(\alpha )<\nu _{1}.}$

${\displaystyle k<\omega \implies \vert \{\alpha :X(\alpha )<k\}\vert <\aleph _{0}.}$

For Ω ≤ α < LUB, Λ (α) has cofinality ω and, if its complexity is defined, we can choose its fundamental sequence to be:

${\displaystyle \rho _{0}=0<\Omega }$

${\displaystyle \rho _{n+1}=\sup\{\Lambda (\beta ):D(\beta )\leq \max(\rho _{n},D(\alpha ))\land \beta <\alpha \land X(\beta )\leq n\}<\Omega }$

${\displaystyle \rho _{\omega }=\sup\{\rho _{n}:n<\omega \}<\Omega .}$

Notice that

${\displaystyle D(\rho _{n})=\rho _{n}<\Omega \leq \alpha }$

${\displaystyle \rho _{n}<\rho _{n}+1=\Lambda (\rho _{n})\leq \rho _{n+1}}$

So the set in the definition of ρ_n+1 is non-empty. Thus the sequence is well defined and strictly increasing. We will see that

${\displaystyle \rho _{\omega }=\Lambda (\alpha ).}$

If there were a β for which

${\displaystyle \beta <\alpha \land \Lambda (\beta )=\rho _{\omega },}$

then

${\displaystyle D(\beta )<\rho _{\omega }}$

so for some n < ω,

${\displaystyle D(\beta )\leq \rho _{n}\land X(\beta )\leq n}$

${\displaystyle \Lambda (\beta )\leq \rho _{n+1}<\rho _{\omega }=\Lambda (\beta ),}$

a contradiction!

Thus

${\displaystyle \rho _{\omega }\in \{\gamma :D(\alpha )<\gamma <\Omega \land \forall \beta <\alpha \,(\gamma \neq \Lambda (\beta ))\},}$

which is the set of which Λ (α) is defined to be the infimum. So

${\displaystyle \Lambda (\alpha )\leq \rho _{\omega }.}$