Ordinal Notation

Definition of the General Notation

In this paper, we define several ordinal notation systems based on the general notion of degree and the corresponding collapsing function C.

Definition: A degree for a well-ordered set S is a binary relation on S such that

1. Every element a has degree 0_S (the least element of S). 0_S only has degree 0_S.
2. For a limit b, 'a' has degree b iff it has every degree less than b.
3. For a successor b'=b+1, either of the following holds
   • An element has degree b' iff it is a limit of elements of degree b
   • There is a limit element d ≤ b such that for every c in S, c has degree b' iff it has degree b and either c ≤ d or c is a limit of elements of degree b (or both).

The corresponding collapsing function C is defined such that:
C(a, b) is the least element above b that has degree a. C(a, b) is defined iff such an element exists.

C is called a collapsing function because typically, if a is much larger than b, then C(a, b) < a and acts as a collapse of a above b.

A partial ordinal notation system is a partial mapping O of ordinals into finite sequences of symbols and ordinals such that O(a) is undefined if a belongs to a sequence in the range of O. (Thus, ordinals are represented in terms of symbols and non-representable ordinals.)

• If an ordinal a is in the domain of O, then represent a using O and the representations of ordinals in O(a).
• Otherwise if a = C(b, c) where b is maximal and c is minimal (that is b'>b ⇒ C(b', c) > C(b, c), and c' < c ⇒ C(b, c') < C(b, c)), then represent a through C(b, c).

1. Let Ω be the least ordinal that is above all ordinals that are represented by C-terms (a C-term is just C(…, …)). C(a, b) is defined whenever a and b are representable and min(a, b) < Ω.
2. Let a be the least ordinal represented by a C-term and Ω as above. If a ≤ C(b,c) < Ω and b is maximal and c is minimal in C(b, c), then C(b, c) is represented by C-term except possibly when c=0 and b is not represented by a C-term.
   Note: In general, we can stack ordinal notation systems on top of each other. For example, we can use one system for ordinals below Ω, and another system for representing ordinals above Ω in terms of ordinals below Ω.
3. The standard representation of an ordinal is the unique representation using (C and 0) with the least number of C-terms. This should hold even if all representable ordinals below a particular one were to be added to O as symbol constants.

An example is the notation system below ε₀ generated using 0 as the least ordinal and C(a, b) = b+ω^a. The standard representation is analogous to Cantor normal form. Another example is generated by 0, x→ε_x, and C with C(a, b) = b+ω^a.
Each of the notation systems in this paper can also be built on top of an arbitrary ordinal by representing all ordinals below that one by a constant.

Basic Properties

If a is maximal in C(a, b), then C(a, b) < C(c, d) iff C(a, b) ≤ d or (b < C(c, d) and a < c).
Since the standard form requires a to be maximal in C(a, b), the above equivalence leads to a polynomial time comparison algorithm for ordinals in the notation system assuming that we can compare a and b when "a" is a constant or is otherwise not a C-term.
Note that to evaluate C(a, b) < C(c, d), c need not be maximal in C(c, d). In fact, recursive definitions of maximality will often involve such comparisons.

Bachmann-Howard Ordinal

We illustrate the framework by defining a notation system at the level of the Bachmann-Howard ordinal. The notation system will consist of C (as above) and two constants: 0 (the least ordinal) and Ω with C(a, b) < Ω if b < Ω. At this point, the notation system is fully specified except for the definition of when a is maximal in C(a, b). On the other hand, at this point the system is fully general in that by choosing the maximality condition, we can reach arbitrarily high recursive ordinals. Note that the definition of maximality cannot affect comparison of ordinals in the standard representation. Instead, it determines which representations are standard. To reach the Bachmann-Howard ordinal, define a to be maximal in C(a, b) iff its standard representation (equivalently, some representation) in terms of ordinals not above b (equivalently, ordinals below C(a, b)) only uses ordinals below a.

Consequently, for C(Ω*a+b, c) (a, b, c < Ω), we have either Ω*a+b or Ω*(a+1) or Ω²is maximal. C(Ω², c) is the least ordinal in the range of Γ above c. If Ω*a+b is maximal and a > 0, then C(Ω*a+b, c) is point number ω^b above c in the range if the ath fixpoint function (ε is the first fixpoint function).

If H(a, b) is the defined as the least set of ordinals including Ω and all ordinals below b and closed under x,y → C(x, y) where x<a, then
C(a, b) = H(a, b+1) ∩ Ω for b < Ω. (If Ω < b, then C(a, b) = b+ω^a.)
Note: H would be unchanged if "closed under x,y → C(x, y)" is replaced by "closed under x,y → C(x, y) where x is maximal and y is minimal in C(x, y)".

To convert C(a, b) to the standard form, convert a and b to the standard form, maximize a and minimize b. b can be minimized using C(x, C(y, z)) = C(x, z) if y < x and y is maximal in C(y, z) (and if b = Ω (or 0), then it is already minimal). To maximize a, if a < Ω and not already maximal, then just replace a with Ω. If a ≥ Ω (and not already maximal), then look at the standard representation of a in terms of ordinals below Ω. Find the rightmost ordinal instance whose standard representation in terms of ordinals below b+1 uses an ordinal above a. Replace that instance with Ω and delete all ordinals (including Ω) to the left of it, removing extraneous Cs (by recursively replacing C(,x) with x and deleting C(,)).
For example, if b = 0 and a = Ω*ω+Γ₀*2+1 = C(0, C(Γ₀, C(Γ₀, C(C(0, Ω), Ω)))), then out of (0, Γ₀, Γ₀, Γ₀, 0), delete the first two and convert the third one to Ω: a → C(, C(, C(Ω, C(C(0, Ω), Ω)))) → C(Ω, C(C(0, Ω), Ω)) = Ω*(ω+1).

In this section, we define an ordinal notation system for rudimentary set theory plus "for every ordinal a, there is recursively a-inaccessible ordinal". Note that instead of rudimentary set theory (a set theoretical analogue of ACA₀), we can use a stronger theory like Π¹₁-CA₀.

Definition of the Notation

The notation is built from the constant 0 (the least ordinal) and a function C as follows:

1. C(a, b, c) is the least ordinal e of admissibility degree a that is above c and is not in H(b, e).
2. H(b, e) is the least set of ordinals that contains all members of e, and is closed under h, i, j → C(h, i, j) where i < b.
3. If an ordinal e is of admissibility degree a, then C(h, i, j) < e whenever h < a and j < e. 0 is of admissibility degree 0.

A canonical notion of admissibility degrees is:
3'. Ordinals of admissibility degree a+1 are the recursively a-inaccessible ordinals and their limits.
For limit a, having admissibility degree a is the same as having every admissibility degree below a.
(An ordinal is recursively a-inaccessible iff it is admissible >ω and for every b < a is a limit of recursively b-inaccessible ordinals.).

1, 2, and 3 define the comparison relation for ordinals in the notation. 1, 2, and 3' uniquely fix C and imply 3.

Interpretation: C(a, b, c) is the least ordinal above c of degree a that is not reachable from below using "collapses" of ordinals less than b. If C(a, b, c) < b, then C(a, b, c) may be viewed as a collapse of b above c.
Note: The pair (a, b) may be viewed as a degree in a similar sense as degrees in the General Notation section.

Comparison Relation

A polynomial time comparison algorithm is obtained as follows:

1. In C(a, b, c), treat (a, b) like an ordinal and use the comparison relation in the General Notation section. Specifically, if a and b are maximal in C(a, b, c), then C(a, b, c) < C(d, e, f) iff C(a, b, c) ≤ f or (c < C(d, e, f) and (a, b) < (c, d)
   Note: (a, b) < (c, d) iff a < c, or a = c and b < d.
2. a is always maximal in C(a, b, c).
3. b is maximal in e = C(a, b, c) iff b is in H(b, e).
4. k is in H(b, e) iff k < e,  or  k = C(g, h, i), h is maximal, i is minimal, each of g, h, i is in H(b, e), and h < b.

Instead of 3 and 4, we can use the following: b is maximal in C(a, b, c) iff it has a representation (equivalently, standard representation) in terms of ordinals below C(a, b, c) (used as constants) using only ordinals below b.

Examples

We define a strong ordinal notation system as follows. Let Ω be a large ordinal and let O be a notation system for ordinals in terms of ordinals below Ω (ordinals below Ω are treated as given in O). For example (and for definitiveness), let O be built using Ω and C with C(a, b) = b + ω^a (b ≥ Ω; in the standard form b = Ω or b ≥ max(ω^a, Ω)). Other canonical examples include Cantor and Veblen normal forms base Ω.
The notation uses C(a, b) for b < Ω (which for ordinals in the notation implies C(a, b) < Ω), and O for larger ordinals, and 0 for the least ordinal. a is maximal in C(a, b) iff for every ordinal d which is included in the O representation of a, the following holds. The standard representation of d does not use ordinals that are below Ω but greater than d, excluding instances in the scope of an ordinal less than C(a, b). (If d is …f…, and f < C(a, b), then do not parse f for ordinals larger than d. If a < Ω, then d is a.)

Examples
Using a canonical O, and setting gaps in the canonical way, we have
C(Ω*a+b, c) = C(a, b, c) of the previous notation (for a, b, c representable in that notation).
Ordinals (below Ω) of degree Ω^a+1 are recursively a-Mahlo ordinals (and their limits)
C(C(Ω, C(Ω², 0)), 0) is the ordinal for KPM (KP + the universe is recursively Mahlo).
In general, for many appropriate conditions F, the ordinal for KP + "the universe is F" is C(C(Ω, a), 0) (which equals C(ε_a+1, 0)) where a is the least ordinal such L_a satisfies or can be forced to satisfy F.
However, the ordinal for KP + "for every ordinal a, there is recursively a-inaccessible ordinal" is C(C(Ω², 0) + ε_a+1, 0) since C(Ω², 0) is needed to reach a = C(Ω*C(Ω², 0) + Ω, 0), the least ordinal a that is recursively a-inaccessible.
Ordinals below Ω of degree Ω^Ω are Π₃ reflecting ordinals (and their limits).
Ordinals below Ω of degree Ω^Ωn (0 < n < ω) are Π_n+2 reflecting ordinals and their limits.
C(C(Ω, C(Ω^Ωn, 0)), 0) is the proof theoretical ordinal of KP + Π_n+2 reflection (0 < n < ω).
C(C(Ω^Ωω, 0), 0) is the proof theoretical ordinal of KP + {Π_n reflection}_n, and also of ACA₀ + lightface Π¹₂ comprehension.
Ordinals above a and below Ω of degree Ω^Ωω*a+1 are a-stable ordinals and their limits.
C(Ω^{ΩC(ΩΩΩ,0)+1},0) is the least ordinal a that is a-stable.
C(Ω^ΩΩ, 0) is the least ordinal a that is a⁺-stable.
C(Ω^ΩΩ*Ω+Ω, 0) is the least ordinal a that is a⁺*a⁺+a⁺-stable, and analogously for other ordinals.
Note: a⁺ is C(Ω, a).

An ordinal that is a limit of ordinals of maximum degree a has degree a+b iff it is a "level" b limit of ordinals of degree a. For example, C(Ω^Ω+Ω²+Ω+1, 0) is the least limit of admissible limits of recursively Mahlo limits of Π₃ reflecting ordinals. An ordinal below Ω has degree a+Ω iff it is not above a certain ordinal and has degree a, or it is an admissible limit or a limit of admissible limits of ordinals of degree a.
An analogous property holds for ordinals of degree a*b. For example, C(ω^Ω3+Ω2*2+Ω, 0) is the least ordinal that is Π₂ reflecting onto ordinals that are Π₃ reflecting onto ordinals that are Π₃ reflecting onto Π₄ reflecting ordinals.

In the case O is based on Ω and C, a natural construction order for representable ordinals is the following: Start with 0, and then iteratively add the least ordinal that equals C(a, b) for a and b already constructed, with Ω added at stage ε₀. The following properties should hold. The construction order for representable ordinals below C(Ω, 0) agrees with their ordinal order. The construction order would remain unchanged if when adding C(a, b), we required that C(a, b) is in the standard form. The order-type of the construction order equals the order type of representable ordinals below C(Ω, 0). The construction order can also be relativized by starting with all ordinals (or all representable ordinals) below a particular one; such construction order should still satisfy analogues of the above properties.

Note that we are not defining C(a, b) when both a and C(a, b) are in a gap in the notation. One possibility is to allow ordinals not representable in the notation from below (that is using lesser ordinals as constants) to have the largest possible degrees. However, in that case some ordinals below C(Ω, 0) would have every degree below Ω (which contradicts the general definition of C).

The notation system can just as well be defined above an arbitrary ordinal. Since O is a parameter, we can "stack" an ordinal notation on top of "itself" any finite number of times. However, stacking the notation system on top of itself an infinite number of times would lead to an ill-founded system.

Comparison Algorithm

1. '0' and 'Ω' are standard
2. If 'C(a,b)' is standard, then so are 'a' and 'b'.
3. If C('a', C('b', 'c')) is standard, then a≤b
4. If the above tests succeeded for "C(a,b)", let T_a be the parse tree of 'a': T_a is the set of subterms of 'a', and for x and y in T_a, x<y means that y is a subterm of x and y≠x. Let Ord(x) be the ordinal coded by x. Parse 'a' into the set of terms below Ω. Formally,
   let X = {x ∈ T_a: Ord(x) < Ω ∧ ∀y<x Ord(y)≥Ω}
   The test for the standard form is:
   ∀x∈X ∀y>x (Ord(y)<Ord(x) ∨ Ord(y)≥Ω ∨ ∃z≤y Ord(z) < C(a, b))
   Note: All comparisons between ordinals here can be done in the above-described lexicographical order.

The notation system below is only slightly more powerful, yet by introducing the idea of "correctness", it brings us significantly closer to full second order arithmetic. Originally, the notation system was my attempt to reach the full second order arithmetic, yet the maximality condition used here gives a much weaker strength.

Here is the notion of correctness used in this section:
Every ordinal has correctness 0.
An ordinal a has correctness 1 if it is admissible >ω.
An ordinal a has correctness of n+1 (n>0) if it is a⁺⁺-stable limit of ordinals of correctness n.
a⁺⁺ is the second admissible ordinal above a.
Note:
a is b-stable iff L_a ⊰_Σ1 L_a+b.
Below, limits of ordinals of correctness n (with correctness n as defined above) will also be said to have correctness n.
A more natural notion of correctness is used in the next section.

The notation system reaches KP + {there is an ordinal of correctness n}_n. This is weaker than even KP + there is a that is a⁺⁺+1-stable, which is weaker than Π¹₁-CA₀ + lightface Π¹₂ comprehension.

For every positive integer i, the constant Ω_i is for the least ordinal of correctness i. (In the above, Ω corresponds to Ω₂.) C(a, b) has correctness n>0 iff there is c with correctness n+1 and b < c ≤ a. Every ordinal has correctness 0, and if m < n, every ordinal of correctness n has correctness m.
Thus, if an ordinal a has a positive but not infinite correctness n, b < a, and d is less than the least ordinal above a of correctness n+1, then C(d, b) < a.

For Ω of correctness at least two, the maximality condition in the notation in the previous section is a necessary but not a sufficient one. We propose the following condition, which implies the previous one.

If C(a, b) has maximum correctness n>0, let Ω be the least ordinal above b of correctness n+1, and Ω' the least ordinal above b of correctness n+2. Thus, we have Ω ≤ a < Ω'. For maximality of a, we require that the standard representation of a does not use ordinals that are above a but below Ω' except in the scope of an ordinal less than Ω. In addition, as in the previous section, parse "a" from the root to branches until a constant or an ordinal below Ω is reached on every branch (at this stage, do not parse the ordinals below Ω). For every such ordinal d < Ω, we require that its standard form does not use ordinals strictly between d and Ω except in the scope of an ordinal less than C(a, b). If C(a, b) only has correctness 0, we simply require that the standard form of a does not use ordinals strictly between a and Ω except in the scope of an ordinal less than C(a, b), where Ω is the least ordinal above b of correctness 2.

The least ordinal of correctness n>0 above b equals f^(i-n)(Ω_n) whenever n≤i and f(x)=C(x, b).
0 < Ω₁ < Ω₂ < …
C(a, b) < Ω_i iff b < Ω_i and a < Ω_i+1.
C(a, b) = Ω_i iff b < Ω_i and a = Ω_i+1.
The maximum degree of C(a, b) can be found by relying on the Ω ≤ a < Ω' above.
Ω_i is always maximal in C(Ω_i, b) (and as always, 0 is maximal in C(0, b)). The leads to a polynomial time algorithm for checking whether a particular representation is standard, and for comparing ordinals in the standard form. I conjecture that there is also a polynomial time algorithm for converting arbitrary C-terms to the standard form.

Examples:
If a has correctness n>0 (but not infinite correctness) and b is the least ordinal above a of correctness n and c < a, then C(ε_{a + 1}, c) = C(b, c).
C(Ω_n+1*2, 0) is the least admissible limit of ordinals of correctness n.
C(Ω_n+1², 0) is the least recursively Mahlo limit of ordinals of correctness n.
If a is the least ordinal above b of correctness n+1, then C(a+a, b) is the least admissible limit of ordinals of correctness n above b, and analogously with other large ordinal properties.

• An ordinal κ has correctness 1 iff it is admissible >ω or is a limit of admissible ordinals.
• An ordinal κ has correctness n+1 with n>0 iff L_κ is a Σ_n elementary substructure of L_ρ.

It is likely that by tweaking the notion of maximality in the previous section, we can reach the full second order arithmetic. Here are possible values for proof-theoretical strength.
C(C(C(Ω₃, C(Ω₃+1, 0)), 0), 0) -- the ordinal for Π¹₂-CA + TI.
C(Ω₃*2, 0) -- the least ordinal κ of correctness 2 with L_κ satisfying KP + Δ₂ separation.
C(C(C(Ω₃*2, 0), 0), 0) -- the ordinal for Π¹₂-TR₀.
C(C(C(Ω₃, C(Ω₃*2, 0)), 0), 0) -- the ordinal for Δ¹₃-CA + TI.
For n>0, C(…C(Ω_n+1+1, 0)…, 0) (with n+1 Cs) -- the ordinal for Π¹_n-CA₀.

To go beyond second order arithmetic, we need transfinitely many degrees of correctness. Cardinals will be ordinals that cannot be reached from below no matter how large the degree of correctness is. Let Ω be the least uncountable cardinal and b a countable ordinal, as computed in the model. If a < b, then b having correctness ω*(a+1) may be defined as L_b+a being elementarily embeddable L_Ω+a. Correctness Ω+ω may correspond to L_b+b being elementarily embeddable in L_Ω+Ω, and similarly for Ω²+ω and L_Ω*Ω, and so on.

For a notation, we can try to use a total ternary function C such that C(a, b, c) is the least ordinal above c of correctness a and for that correctness of degree b. If we treat (a, b) like an ordinal, then the function satisfies formal requirements of C (as described in the general notation), so the only issue is specifying when (a, b) is maximal. For a=0, the maximality of b is like in the second section (that is the standard form of b uses only ordinals below b), but the general case is unclear.