User:JRSpriggs/Ordinal notation

Generalizing the ξ notation

We can generalize the ξ notation to a much stronger notation. First we define an auxiliary function D which serves to protect against circular definitions of ordinals. There are cases:

$\alpha <\Omega \to D(\alpha )=\alpha .$

$\Omega \leq \alpha <\Gamma _{\Omega +1}\land \alpha \neq \Omega ^{\alpha }\land \,\alpha =\Omega ^{\beta }\cdot \gamma \,+\,\delta \,\land 1\leq \beta \land 1\leq \gamma <\Omega \land \delta <\Omega ^{\beta }\to D(\alpha )=\max(D(\beta ),\gamma ,D(\delta )).$

$\Omega \leq \alpha <\Gamma _{\Omega +1}\land \alpha =\Omega ^{\alpha }\land \,\alpha =\phi _{\eta }(\beta )\,\land 1\leq \eta <\alpha \land \beta <\alpha \to D(\alpha )=\max(D(\eta ),D(\beta )).$

Now, we can define Λ by

$\Lambda (\alpha )=\inf\{\gamma <\Omega \,\vert \,D(\alpha )<\gamma \land \forall \beta <\alpha \,(\gamma \neq \Lambda (\beta ))\}$

via transfinite recursion on α. This is an injective function from Γ_Ω+1 to Ω itself. Then for α, β < Ω,

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

It is also related to the binary Veblen functions by

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

where α, β < Ω and k is either 0 or 1. One can show that

$\Lambda (\alpha )<\Lambda (\beta )\leftrightarrow (\alpha <\beta \land D(\alpha )<\Lambda (\beta ))\lor (\beta <\alpha \land \Lambda (\alpha )\leq D(\beta )).$

This notation is a kind of Ordinal collapsing function, but we choose injectivity over continuity.

To evaluate D (α), we only need to compute the value of D on a finite number of ordinals. Given an ordinal β < Ω, there are only a countable number of ordinals α for which

$D(\alpha )<\beta .$

Here we prove that Λ is, in fact, defined on its entire intended domain Γ_Ω+1. 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.

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

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

$\rho _{\omega }=\sup\{\rho _{n}\vert n<\omega \}<\Omega$

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

because if

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

then

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

so for some n < ω,

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

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

a contradiction!

Identifying important ordinals with Λ:

• First infinite ordinal $\omega =\Lambda (\Omega )$
• First epsilon number $\epsilon _{0}=\Lambda (\Omega ^{2})$
• Feferman–Schütte ordinal $\Gamma _{0}=\Lambda (\Omega ^{2}\cdot 2)$
• Small Veblen ordinal $\Lambda (\Omega ^{\omega })$
• Large Veblen ordinal $\Lambda (\Omega ^{\Omega })$
• Bachmann–Howard ordinal $\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 little information available in Wikipedia. The Ackermann ordinal is probably Λ (Ω³) or maybe Λ (Ω²·3) or Λ (Ω⁴).

I think that Buchholz's ordinal might be Λ(ε_Ω·ω) and the Takeuti–Feferman–Buchholz ordinal might be Λ(ε_Ω·ω+1).

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

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

$\eta _{n+1}=\phi _{\eta _{n}}(0)$

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

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

Then ρ_ω will be the next ordinal after ν which not in the image of Λ. Also any limits of ordinals not in the image are also not in the image. If ρ_ω were in the image of Λ, then for some α

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

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

so for some n < ω,

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

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

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

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

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

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

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

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

Comparison with finitary Veblen hierarchy: In what follows, α, β, γ are less than Ω and j, k, m are less than ω.

If α is less than ω, then

$\Lambda (\Omega ^{2}\cdot (\alpha +1)+\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.

Otherwise,

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

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

$\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)$.

For example,

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

OK? JRSpriggs (talk) 22:39, 21 May 2022 (UTC)

Old version

The following is a write-up of my system of ordinal notations. See also Large countable ordinal, Ordinal notation, and Ordinal collapsing function.

As I said at Talk:Ordinal notation, "An ordinal notation is something which denotes an ordinal, that is, it is a way of naming an ordinal so that we can communicate about them with others and with ourselves.". To this end, I tried to provide a unique notation for as many ordinals as possible. Each ordinal is to be described in terms of strictly smaller ordinals, except that a quantifier-like functional is used whose bound variable ranges over some larger ordinals (these may be taken as members of the closed unbounded class of ordinals indiscernable for L which exist if 0^# exists; otherwise use uncountable regular ordinals).

The pairing function

As described at Ordinal notation#ξ-notation, the system begins with a zero-ary function for zero, 0, and a binary pairing function, ξ (α, β), that takes care of all non-zero ordinals except the epsinums (epsilon numbers, i.e. those α for which α = ω^α).

If we restrict the pairing function ξ (α, β) to Ω×Ω (where Ω is an uncountable regular ordinal such as ω₁), we can define it by transfinite recursion on Ωα+β. Let ξ(α,β) = the smallest ordinal γ such that α < γ and β < γ and γ is not the value of ξ for any smaller α or for the same α with a smaller β.

At each stage Ωα+β in the construction of ξ, the set of nonzero ordinals not in the range of ξ yet is a closed unbounded subset of Ω.

Closedness: At stage zero, 0 is removed leaving [1,Ω) which is closed in Ω. At successor stages, we are removing one element (ξ(α,β)) which will not destroy the closedness, if it is not a limit point of the remainder. If it were a limit point of the remainder, then there would be an element of the remainder strictly between max(α,β)and ξ(α,β) in which case ξ(α,β) would not be the smallest ordinal in the remainder larger than α and β, a contradiction to the definition. At limit stages, we take the intersection of the sets of remaining ordinals at earlier stages which is closed because any intersection of closed sets is closed.

Unboundedness: Removing one ordinal from the unbounded remainder will not cause it to cease to be unbounded, so the only issue is at limits when one takes infinite intersections.

• Suppose that the remainder is unbounded at all stages before stage Ωα+β and β is a limit ordinal. For any potential bound γ, let ρ₀=γ+1. Let ρ_η+1 be the smallest ordinal greater than ρ_η which is remaining at stage Ωα+η for η<β. At limits η≤β, let ρ_η be the limit of earlier ρs (smaller than Ω by regularity) which will belong to all those earlier remainders and thus to their intersection at this stage. Thus ρ_β is an arbitrarily large ordinal remaining at the Ωα+β stage, i.e. the remainder at this stage is unbounded.
• Suppose that the remainder is unbounded at all stages before stage Ω(α+1)=Ωα+Ω. For any potential bound γ, let ρ₀=max(α,γ)+1. Let ρ_n+1 be the smallest ordinal greater than ρ_n which is remaining at stage Ωα+ρ_n. Let ρ_ω be the limit of those ρs. Then ρ_ω must be in the remainder at the Ωα+Ω stage. For if it were not, then ρ_ω=ξ(α,β)>β, but there must be an n such that β<ρ_n<ρ_ω and thus ρ_n+1 must be in the remainder at stage Ωα+β and be larger than both α and β contradicting the choice of ξ(α,β) as the smallest such ordinal.
• Suppose that the remainder is unbounded at all stages before stage Ωα and α is a limit ordinal. For any potential bound γ, let ρ₀=γ+1. Let ρ_η+1 be the smallest ordinal greater than ρ_η which is remaining at stage Ωη for η<α. At limits η≤α, let ρ_η be the limit of earlier ρs (smaller than Ω by regularity) which will belong to all those earlier remainders and thus to their intersection at this stage. Thus ρ_α is an arbitrarily large ordinal remaining at the Ωα stage, i.e. the remainder at this stage is unbounded.
• Consider stage Ω² which is after all ξ(α,β) have been removed. The above showed that the remainder is unbounded at all earlier stages. For any potential bound γ, let ρ₀=γ+1. Let ρ_n+1 be the smallest ordinal greater than ρ_n which is remaining at stage Ωρ_n. Let ρ_ω be the limit of those ρs. Then ρ_ω must be in the remainder at the Ω² stage. For if it were not, then ρ_ω=ξ(α,β)>max(α,β), but there must be an n such that max(α,β)<ρ_n<ρ_ω and thus ρ_n+1 must be in the remainder at stage Ωα+β and be larger than both α and β contradicting the choice of ξ(α,β) as the smallest such ordinal.

Alternatively, one could argue that the remainder must be unbounded at all stages because if it were not then one could construct a naming scheme for all ordinals less than Ω by using 0, ξ, and constant symbols for all the ordinals remaining at stage Ω² which would give us a mapping from a cardinal less than Ω onto Ω which is impossible.

The value of ξ(α,β) is independent of the choice of which uncountable regular ordinal one uses for Ω provided that Ω>max(α,β). Let ξ₁ be defined relative to Ω₁ and let ξ₂ be defined relative to Ω₂ where Ω₂>Ω₁. If there were a difference, let ξ₁(α,β)≠ξ₂(α,β) be the first such difference, i.e. Ω₁α+β is minimal for such a difference. The difference could not be attributed to the constraint that ξ(α,β)>max(α,β) since that is the same in both cases. So we only have to show that the remainder below Ω₁ at stage Ω₁α+β is the intersection of Ω₁ with the remainder below Ω₂ at stage Ω₂α+β. The only way that the remainder could be different is if for some γ and δ, ξ₂(γ,δ)<Ω₁ even though either γ>Ω₁ or δ>Ω₁. But that is impossible because then Ω₁<max(γ,δ)<ξ₂(γ,δ)<Ω₁.

The system

The terms are:

• "0" is a term with no free variables.
• If "A" and "B" are replaced by terms, then "ξ (A, B)" is a term. Its set of free variables is the union of the sets of free variables in "A" and "B".
• If "n" is a natural number, then "Κ_n" is a term whose set of free variables is its own singleton. For example, "Κ₀" is a term whose set of free variables is {Κ₀}. Such a Κ_n is called a key and, in this context, n is called its index.
• If "A" is replaced by a term and every "Κ_j" which is free in "A" satisfies i ≤ j, then "Λ_i (A)" is a term whose set of free variables is the same as that of "A" except that "Κ_i" is excluded. In this context, i is called the index of Λ_i (A); and A is called its code.

There is a total ordering on the terms given by:

• terms have equal value only when they are identical.
• 0 < A unless A is 0.
• ξ (A, B) < ξ (C, D) iff ( A < C and B < ξ (C, D) ) or ( A = C and B < D ) or ( A > C and ξ (A, B) ≤ D ).
• ξ (A, B) < Κ_i iff ( A < Κ_i ) and ( B < Κ_i ).
• ξ (A, B) < Λ_i (C) iff ( A < Λ_i (C) ) and ( B < Λ_i (C) ).
• Κ_j < Κ_i iff i < j. Notice the reversed ordering of these keys. Thus the terms including free variables are not well-ordered unless the index is bounded below ω.
• Κ_i < Λ_j (A) iff some Κ_l occurs free in Λ_j (A) for l ≤ i.
• Λ_i (A) < Λ_j (B) iff ( i < j and every i-part of A is < Λ_j (B) ) or ( i = j and A < B and every i-part of A is < Λ_J (B) ) or ( i = j and A > B and Λ_i (A) ≤ some j-part of B ) or ( i > j and Λ_i (A) ≤ some j-part of B ).

where:

• If Κ_i is not free in A, then the i-parts of A are { A }. In particular, the i-parts of Κ_j for i < j are { Κ_j }.
• Otherwise, the i-parts of ξ (A, B) are the union of the i-parts of A and the i-parts of B.
• The i-parts of Κ_i are the empty set { }.
• The i-parts of Λ_j (A) [for j < i, of course] are the i-parts of the j-parts of A.

The (well-ordered) ordinal notations are those terms which have no free variables.

Interpretation of Lambda zero

Let the key, $\mathrm {K} _{0}\,,$ be some unspecified uncountable regular ordinal. Notice that $\epsilon _{\mathrm {K} _{0}+1}\,$ is the least epsinum greater than $\mathrm {K} _{0}\,,$ that is, the smallest ordinal larger than the key which cannot be described using the pairing function and ordinals less than or equal to the key.

Define $D_{0}(\alpha )\,$ for ordinals $\alpha <\epsilon _{\mathrm {K} _{0}+1}\,$ by:

• $D_{0}(\alpha )=\alpha \,$ for $\alpha <\mathrm {K} _{0}\,$;
• $D_{0}(\mathrm {K} _{0})=0\,$; and
• $D_{0}(\xi (\alpha ,\beta ))=\max(D_{0}(\alpha ),D_{0}(\beta ))\,$ otherwise.

Let $\Lambda _{0}(\alpha )\,$ be the least ordinal β such that β is an epsinum (neither 0 nor in the range of ξ) and $D_{0}(\alpha )<\beta \,$ and $\beta \neq \Lambda _{0}(\gamma )\,$ for any $\gamma <\alpha \,.$

Notice that $D_{0}(\alpha )\,$ is the maximum of the 0-parts of A when A is a term for the ordinal α.

Relationship to the Veblen hierarchy

See Veblen function. For $\alpha <\mathrm {K} _{0}\,$, either $\Lambda _{0}(\alpha )=\epsilon _{\alpha }=\varphi _{1}(\alpha )\,$ or $\Lambda _{0}(\alpha )=\epsilon _{\alpha +1}=\varphi _{1}(\alpha +1)\,.$ Remember that ξ (0, α) = α+1.

More generally, $\Lambda _{0}(\mathrm {K} _{0}\cdot \alpha +\beta )=\varphi _{1+\alpha }(\beta +k)\,$ for $\alpha ,\beta <\mathrm {K} _{0}\,$ and k = 0 or 1. If $\varphi _{\alpha }(0)=\alpha \,$ and $\beta <\omega \,,$ then k = 1. Otherwise, if $\varphi _{1+\alpha }(\gamma )=\gamma \,$ and $\gamma \leq \beta <\gamma +\omega \,,$ then k = 1. Otherwise, k = 0.

Relationship to special large countable ordinals

$\omega =\xi (\xi (0,0),0)\,.$ $\epsilon _{0}=\Lambda _{0}(0)\,.$

The Feferman–Schütte ordinal is $\Lambda _{0}(\mathrm {K} _{0}^{2})=\Lambda _{0}(\xi (\mathrm {K} _{0},\mathrm {K} _{0}))\,.$

The Ackermann ordinal might be $\Lambda _{0}(\mathrm {K} _{0}^{3})=\Lambda _{0}(\xi (\mathrm {K} _{0},\xi (\mathrm {K} _{0},\mathrm {K} _{0})))\,.$

The small Veblen ordinal might be $\Lambda _{0}(\mathrm {K} _{0}^{\omega })=\Lambda _{0}(\xi (\xi (0,\mathrm {K} _{0}),0))\,.$

The large Veblen ordinal might be $\Lambda _{0}(\mathrm {K} _{0}^{\mathrm {K} _{0}})=\Lambda _{0}(\xi (\xi (\mathrm {K} _{0},0),0))\,.$

The Bachmann–Howard ordinal might be $\Lambda _{1}(0)\,.$

Interpretation of Lambda one

Let $\mathrm {K} _{1}\,$ be some unspecified uncountable regular ordinal; and let $\mathrm {K} _{0}\,$ be a larger unspecified uncountable regular ordinal.

Define $D_{1}(\alpha )\,$ for ordinals α less than the supremum as n goes to ω of $\Lambda _{0}(\Lambda _{0}(...\Lambda _{0}(\mathrm {K} _{1})...))\,$ where the function $\Lambda _{0}\,$ has been applied n times by:

• $D_{1}(\alpha )=\alpha \,$ for $\alpha <\mathrm {K} _{1}\,;$
• $D_{1}(\mathrm {K} _{1})=0\,;$
• $D_{1}(\xi (\alpha ,\beta ))=\max(D_{1}(\alpha ),D_{1}(\beta ))\,$ if $\mathrm {K} _{1}\leq \alpha \lor \mathrm {K} _{1}\leq \beta \,;$ and
• $D_{1}(\Lambda _{0}(\alpha ))=\max\{D_{1}(\beta )\vert \beta {\text{ is a 0-part of }}\alpha \}\,$ otherwise.

Let $\Lambda _{1}(\alpha )$ be the least ordinal β such that β is an epsinum which is not in the range of $\Lambda _{0}$ and $D_{1}(\alpha )<\beta$ and $\beta \neq \Lambda _{1}(\gamma )$ for any γ < α.

Notice that $D_{1}(\alpha )$ is the maximum of the 1-parts of A when A is a term for the ordinal α.

The Bachmann-Howard ordinal might be $\Lambda _{1}(0)$.

Inductive hypothesis

I seek to show by transfinite induction on i that the terms for which the value of the indexes are less than i and the free variables are a subset of some given finite set are well-ordered and that the notations (no free variables) among them have values which constitute a transitive set of ordinals. This will be shown by extending any order-preserving mapping of keys to uncountable regular ordinals to a mapping of said terms to ordinals in an order-preserving way.

The induction is done in an omega-sequence of phases. Phase 0 covers all indexes which can be described with 0 and ξ alone, i.e. those which are less than $\epsilon _{0}$. For each natural number n, phase n + 1 uses those new indexes which are values of ordinal notations which use indexes from phase n and earlier phases.

The full system

The full system (which may be inconsistent) is defined here.

The terms are:

• "0" is a term with no free variables.
• If "A" and "B" are replaced by terms, then "ξ (A, B)" is a term. Its set of free variables is the union of the sets of free variables in "A" and "B".
• If "I" is replaced by a term with no free variables, then "Κ_I" is a term whose set of free variables is its own singleton. For example, "Κ₀" is a term whose set of free variables is {Κ₀}. Such a Κ_I is called a "key"; and, in this context, I is called its "index".
• If "I" and "A" are replaced by terms and "I" has no free variables and every "Κ_J" which is free in "A" satisfies "I ≤ J", then "Λ_I (A)" is a term whose set of free variables is the same as that of "A" except that "Κ_I" is excluded. In this context, I is called the "index" of Λ_I (A); and A is called its "code".

There is a (hopefully) total ordering on the terms given by:

• terms have equal value only when they are identical.
• 0 < A unless A is 0.
• ξ (A, B) < ξ (C, D) iff ( A < C and B < ξ (C, D) ) or ( A = C and B < D ) or ( A > C and ξ (A, B) ≤ D ).
• ξ (A, B) < Κ_I iff ( A < Κ_I ) and ( B < Κ_I ).
• ξ (A, B) < Λ_I (C) iff ( A < Λ_I (C) ) and ( B < Λ_I (C) ).
• Κ_I < Κ_J iff J < I. Notice the reversed ordering of these "keys" which is why this cannot be a well-ordering.
• Κ_I < Λ_J (A) iff some Κ_L occurs free in Λ_J (A) for L ≤ I.
• Λ_I (A) < Λ_J (B) iff ( I < J and every I-part of A is < Λ_J (B) ) or ( I = J and A < B and every I-part of A is < Λ_J (B) ) or ( I = J and A > B and Λ_I (A) ≤ some J-part of B ) or ( I > J and Λ_I (A) ≤ some J-part of B ).

where:

• If Κ_I is not free in A, then the I-parts of A are { A }. In particular, the I-parts of Κ_J for I ≠ J are { Κ_J }.
• Otherwise, the I-parts of ξ (A, B) are the union of the I-parts of A and the I-parts of B.
• The I-parts of Κ_I are the empty set { }.
• The I-parts of Λ_J (A) [for J < I, of course] are the I-parts of the J-parts of A.

The (hopefully) well-ordered ordinal notations are those terms which have no free variables.