Dmytro Taranovsky
January 24, 2006
Outline: We define strong yet simple ordinal notation systems. The first section defines the general structure for the notations. The notation in the second section reaches ATR0 plus "for every ordinal a, there is recursively a-inaccessible ordinal." The third section reaches up to Π12-CA0. The final section attempts to reach full second order arithmetic. Proofs are not included.
We first introduce a general structure for the notations. The notation is built from 0 (the least ordinal), other constants, and a total binary function C. C(a, b) is the least ordinal above b that has degree a.
Every ordinal has degree 0. If a<b, then every ordinal of degree b has degree a. A limit of ordinals of degree a has degree a. An ordinal has degree a+1 iff it is a limit of ordinals of degree a or is not above a certain ordinal and has degree a. For a limit ordinal a, an ordinal in the notation has degree a iff it has every degree b<a. C(a, b) = b + ωa iff C(a, b) ≥ a (in particular, if a is less than the least fix-point of x→ωx above b).
The standard representation of the constants are their names, and for other ordinals, it is C(a, b) where a is maximal and b is minimal, and a and b are in the standard form. The standard representation of an ordinal should be the one with least number of applications of C. This should remain true even if all ordinals below a particular one were to be added as a constant.
The ordinals are compared as follows:
Besides the constants, the only unspecified issue is when a is maximal in C(a, b). For example, if a is always maximal, we just have addition and exponentiation. Note that we can compute whether a<b without verifying that b is in the standard form. In fact, definitions of standard forms usually use such computations.
For example, to reach the Bachmann-Howard ordinal, we can add constant Ω with C(a, b)<Ω if b<Ω and an ordinal above a is in the notation. Define a to be maximal if its standard representation (equivalently, some representation) in terms of ordinals not above b (equivalently, ordinals below C(a, b)) only uses ordinals below a.
For C(Ω*a+b, c) (a, b, c < Ω), we have either Ω*a+b or Ω*(a+1) or Ω2is maximal. C(Ω2, c) is the least point 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). The notations below are essentially extensions of this notation.
In this section, we define the notation for rudimentary set theory plus "for every ordinal a, there is recursively a-inaccessible ordinal". The large ordinal hypothesis is equivalent over V=L to (boldface) Δ03 determinacy. Note that instead of rudimentary set theory (a set theoretical analogue of ACA0), we can use a stronger theory like Π11-CA0.
The notation is built from the constant 0 (the least ordinal) and a function C as follows:
A canonical notion of the degrees is:
3'. Ordinals of degree a+1 are the recursively a-inaccessible ordinals and their limits.
For limit a, having degree a is the same as having every 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 also be viewed as a degree and is the notion of degrees used in the other sections.
A polynomial time comparison algorithm is obtained as follows:
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.
We define a strong ordinal notation 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). The notation uses C(a, b) for b<Ω (which for ordinals in the notation implies C(a, b)<Ω), and O for larger ordinals. 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.)
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.
Ordinals (below Ω) of degree Ωa+1 are recursively a-Mahlo ordinals (and their limits)
Ordinals (below Ω) of degree ΩΩ are Π3 reflecting ordinals (and their limits)
C(C(Ω, C(Ω2, 0)), 0) is the ordinal for KPM (KP + the universe is recursively Mahlo, equivalently, KP + Δ1 Monotonic Induction).
In general, for appropriate "…", the ordinal for KP + "the universe is …" is C(C(Ω, a), 0) (which equals C(εa+1, 0)) where a is the least ordinal such La satisfies or can be forced to satisfy ….
However, the ordinal for KP + Δ03 determinacy is C(C(Ω2, 0)+εa+1, 0) since C(Ω2, 0) is needed to reach a = C(Ω*C(Ω2, 0) + Ω, 0), the least ordinal a that is recursively a-inaccessible.
C(C(εΩ+1, 0), 0) is the proof theoretical ordinal of KP+{Πn reflection}n, and also of ACA0 + lightface Π12 comprehension.
C(C(ΓΩ+1, 0), 0) would be (but, below, we define C differently) the ordinal for ATR0 + lightface Π12 comprehension.
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(ΩΩ+Ω2+Ω+1, 0) is the least limit of admissible limits of recursively Mahlo limits of Π3 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.
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 Ω.
The notation 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, thus reaching the proof theoretical ordinal of Π12-CA0.
Full second order arithmetic can be reached by using the idea of "correctness". The following is a canonical definition of correctness. Let ρ be the least ordinal such that Lρ satisfies ZFC minus power set.
For every positive integer i, the constant Ωi is for the least ordinal of correctness i. (In the above, Ω corresponds to Ω2.) 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.
This leads to a polynomial time comparison algorithm. Note that the least ordinal of correctness n>0 above b can be found by taking the least Ωi with i≥n and b<Ωi, and applying x→C(x, b) i-n times.
The three questions about the notation are: Is the notation system well-founded? Does it reach full second order arithmetic? Is it the most canonical way to reach full second order arithmetic?
An issue with the notation is that it does not include the least ordinal a that is stable up to an admissible ordinal above a. A good notation is expected to include all ordinals having a canonical provable representation in the theory. Nevertheless, the present notation has means of obtaining strength. For example, C(C(Ω3+1, 0), 0) is the least ordinal a that is stable up to the analogue of the proof-theoretical ordinal of Π12-CA0 above a.
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( C(Ω3, Ω2) + ΓΩ_2 + 1, 0) is C(ΓΩ+1, 0) of the previous section.
C(C(C(Ω3, C(Ω3+1, 0)), 0), 0) is the ordinal for Π12-CA + TI.
C(Ω3*2, 0) is the least ordinal κ of correctness 2 with Lκ satisfying KP + Δ2 separation.
C(C(C(Ω3*2, 0), 0), 0) is the ordinal for Π12-TR0.
C(C(C(Ω3, C(Ω3*2, 0)), 0), 0) may be the ordinal for Δ13-CA + TI.
C(C(C(Ω3, C(Ω32, 0)), 0), 0) may be the ordinal for KP + Δ2 Monotonic Induction.
For n>0, C(…C(Ωn+1+1, 0)…, 0) (with n+1 Cs) is the ordinal for Π1n-CA0.
Canonical ordinal notation systems are not yet known for uncountable set theory, but some understanding is here today. A key idea is that there are transfinitely many degrees of correctness, and cardinals are 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 Lb+a being elementarily embeddable LΩ+a. Correctness Ω+ω may correspond to Lb+b being elementarily embeddable in LΩ+Ω, Ω2+ω to LΩ*Ω, and so on.
For a notation, we can 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, but the general case is more complicated.