Dmytro Taranovsky

Last Update: December 31, 2018

**Abstract:** We introduce a framework for ordinal notation systems, present a family of strong yet simple systems, and give many examples of ordinals in these systems. While much of the material is conjectural, we include systems with conjectured strength beyond second order arithmetic (and plausibly beyond ZFC), and prove well-foundedness for some weakened versions.

**Contents:**

1 Introduction

1.1 Introduction

1.2 Prior Work

1.3 Goals of Ordinal Analysis

2 A Framework for Ordinal Notations — defines the general structure for the notations.

2.1 Definition of the General Notation

2.2 Basic Properties

2.3 Bachmann-Howard Ordinal

2.4 One Variable C

2.5 Reflection Configurations

3 Degrees of Recursive Inaccessibility — presents a notation system for ATR_{0} plus "for every ordinal *a*, there is recursively *a*-inaccessible ordinal".

3.1 Definition of the Notation

3.2 Comparison Relation

3.3 Examples

4 Degrees of Reflection — presents a notation system for KP + Π_{n} reflection and somewhat stronger systems, with the canonical assignment for nonrecursive ordinals.

4.1 Definition of Degrees of Reflection

4.2 Examples and Additional Properties

4.3 Assignment of Degrees

4.4 A Step towards Second Order Arithmetic

5 Main Ordinal Notation System — presents the main notation system, which plausibly reaches second order arithmetic (Z_{2}) or higher.

5.1 Definition and Basic Properties

5.2 Strength of the Main System

5.3 Old Analysis and Examples

6 Beyond Second Order Arithmetic — gives insights for going beyond second order arithmetic and ZFC

6.1 Old Analysis

6.2 New Analysis

7 Iteration of n-built from below — proposes a strengthening of the main system.

8 Built-from-below with Passthrough — presents a system with conjectured strength beyond second order arithmetic, and uses large cardinals to prove well-foundedness for a weakened version.

8.1 Definition and Properties

8.2 Degrees of Reflection with Passthrough

8.3 Proof of Well-foundedness

8.4 Using Canonical Definitions

**Notes:**

• Claims not marked as theorems or propositions should be treated as conjectures (see Introduction).

• OrdinalArithmetic.py (absolute link) is a python module/program that implements comparison and ordinal arithmetic for the main ordinal notation system. See 2.4 One Variable C subsection of the paper for a notational difference with the module. The reader is encouraged to try out the module.

Ordinals play a core role in set theory, and a good ordinal representation system for a theory gives us a qualitatively enhanced understanding of that theory. However, prior to this paper, we lacked reasonable ordinal notation systems for "strong" theories such as second order arithmetic. One can always extend a system to bigger ordinals, but the key obstacle is complexity. For example, by just intuitively counting past infinity without a plan, one will likely bog down even before reaching ε_{0}. However, a repeated historical pattern is that new ideas greatly simplify the upper reaches of the previous systems and reach new ordinals. It is just such a set of ideas that form the core of this paper. Specifically, we present a framework that it makes it much easier to define new ordinal notation systems, and define and analyze simple yet strong systems following that framework.

**Prerequisites:** The paper assumes basic understanding of ordinals, and parts of the paper assume more. A good introduction is in (Rathjen 2006).

**Note:** This paper was developed over time, and different main sections can mostly be read independently of each other. For example, the reader is free to read the definition of the main system right away.

**What this Paper Accomplishes:** We define and analyze several very strong ordinal notation systems presented as recursive relations between terms. The canonical assignment of ordinals to terms (see 1.3 Goals of Ordinal Analysis below for what that means) is fully given for some weaker systems, and many examples of conjectured canonical assignment are given beyond that. Well-foundedness is proved for some of the systems. Strength lower bounds are not proved.

Formally, unless stated (or the reader is satisfied) otherwise, claims in this paper about the notation systems should be treated as conjectures. While some conjectures are speculative (with significant doubts always noted), in many cases our understanding is so detailed, coherent, and precise as to be very confident in its accuracy. This is not a substitute for proof, but is the best we have before the required bounds are proved.

Prior to the Degrees of Reflection system in this paper, the strongest reasonably simple ordinal notation system was the one for KP + Π_{3} reflection (Rathjen 1994). (That system is referenced in the next paragraph, which the reader without requisite background is free to skip.) Rathjen also proposed stronger systems, but they are so complex that the problem of finding a reasonable ordinal notation system for those systems would be best described as only partially solved.

Superficially, Rathjen's Ψ^{ξ}_{π}(α) (for KP + Π_{3} reflection) looks like C(a,b,c) (or C(ξ,α,π)) in "Degrees of Recursive Inaccessibility". However, while Rathjen does not go beyond ordinary built-from-below construction, he uses a trick that allows ξ to correspond to degree of recursive Mahloness instead of inaccessibility. (Actually, for simplicity his paper uses large cardinals instead of their recursive analogues. Also, while the examples below illustrate his system, I did not verify that the examples hold for all parameters.) Instead of collapsing above c, he collapses below (admissible) π. In his system, π codes both an ordinal above which to do the collapse, as well as the degree to which the resulting ordinal will be a limit of admissibles. If π is a successor admissible, the collapse will be an ordinal above π's admissible predecessor. If π is a successor recursively inaccessible, Ψ^{0}_{π}(α) will be a limit of admissible ordinals and will be above π's recursively inaccessible predecessor, and so on. Admissible ordinals below the least recursively Mahlo ordinal Ξ(2) are obtained using Ψ^{1}_{Ξ(2)}(α), which works since below Ξ(2) the degree of recursive inaccessibility is in a sense recursive. Now, for another example, suppose that π is the least recursively hyper-Mahlo limit of recursively hyper-hyper-Mahlo ordinals above the least recursively hyper-hyper-hyper-Mahlo ordinal Ξ(5). Ψ^{0}_{π}(α) ranges over non-admissible limits of recursively hyper-hyper-Mahlo ordinals above Ξ(5), Ψ^{1}_{π}(α) ranges over admissible limits of such ordinals, and Ψ^{2}_{π}(α) ranges over recursively Mahlo limits of such ordinals.

The downside of Rathjen's approach is the lack of the simple monotonicity that C has, as well additional complexity when trying to extend it (especially beyond Π_{3}-reflection) where simple built-from-below does not suffice. Even more recent systems along these lines are fairly complex. For examples, see (Duchhardt 2008) for Π_{4} reflection, (Arai 2015) for Π_{n} reflection, and (Stegert 2010) for stability.

**History of this paper:** In 2005, I discovered the right general form of C, defined a notation system at the level of *a*-recursively inaccessible ordinals, and proposed a schema (a detailed idea) for reaching second order arithmetic (August 7, 2005 version of the paper). In 2006 (January 24, 2006 revision), I defined the stronger ("Degrees of Reflection") notation system, and (June 28, 2009 revision) added the comparison algorithm subsection (the algorithm was previously given implicitly). Finally, in March 16, 2012 revision, I added the main ordinal notation system, intended for second order arithmetic. Afterwards, in 2014 (January 9, 2014 revision), I discovered new structure in the main system and wrote an initial version of a series of updates. In 2015 (April 20, 2015 revision), I proposed a strengthening of the main system. August 24, 2016 revision added "Built-from-below with Passthrough", and around that time, I made many improvements to the paper. October 9, 2016 revision extended the well-foundedness proof for the passthrough system to a stronger system. August 2017 revision added "Using Canonical Definitions" and updated other parts of the paper. November 2018 revision (1) added the correct canonical assignment for Degrees of Reflection (including a correction at the level of Π_{n} reflection), (2) added reflection configurations, and (3) made expository, organizational and other changes.

Ordinal analysis of set theories gives us a qualitatively new understanding of the theories and of the infinite ordinals that appear in those theories. A good ordinal notation system captures all ordinals that have a canonical definition in the theory. If a theory is compared to a country, a good ordinal notation system can be viewed as a precise map of the country.

The cumulative hierarchy (or at least, enough aspects of the cumulative hierarchy to acts as a scaffold for large cardinal axioms) and various large cardinal axioms are conceptually simple. We expect they can be captured with reasonably simple combinatorial principles into ordinal notation systems, though we do not yet know whether any of the systems in the paper reach that far.

To state the goals more precisely, for simplicity, let us assume that the theory is naturally consistent with the existence of a definable function f such that ∀s∃n∈ℕ s=f(n) (note that, for us, it suffices for s to range over ordinals). If not, we can use a conservative extension of the theory by, for example, a universal Skolem function: ∃tφ(s,t) ⇒ φ(s,F("φ",s)) (φ has two free variables and does not use F) (and an axiom to that effect); alternatively, for many theories, we can add proper classes or their analogues. We are also need a notion of the ordinals; for simplicity, if necessary, let us conservatively extend the theory with ordinals. Sometimes, the most natural extension is nontrivial. For example, for second order arithmetic (or ZF\P) with projective determinacy, we may want to consider Wadge ranks of projective sets instead of just countable ordinals.

In general, it is not clear what canonical means, or even, until we get a suitable ordinal notation system, that it is unambiguous. However, for recursive ordinals, canonical definitions are recursive. If the proof theoretical ordinal of a theory T (T includes Π^{1}_{1} induction) is sup(a_{n}), an example of a non-canonical definition is "sup(a_{n}) if each a_{n} exists, otherwise the largest a_{n} that exists". Intuitively, unlike provably recursive ordinals in T, this ordinal can be given a more direct definition in an extension of T. Moreover, T is consistent with that ordinal already having a notation a_{n}, albeit for an n that is nonstandard outside of T.

Even for a strong appropriate theory T (extended with Skolem functions if necessary), there is a recursive well-ordering '≺' of ℕ (with comparison but not well-foundedness provable in T), and an assignment formula φ:ℕ→Ord (inside T, φ may be partial as a function) such that T is consistent with "every ordinal gets assigned a notation by φ, and ordinal comparison agrees with ≺". The reason is that (at least for appropriate T), T is consistent with there being a cut I of ℕ with every ordinal definable at a definability level in I, with each definability level in a sense transcending previous levels. Now pick a well-ordering '≺' such that T is consistent with '≺' embedding rationals ℚ (and hence ℚ^{<ω}), and proceed by induction on definability level to assign all ordinals to elements of ℚ^{<I}. A far-reaching conjecture is that '≺' and φ can be chosen canonically, thus effectively capturing T.

*Notes on canonicity:*

* It is often easier to skip some canonically definable ordinals, in which case we get only some of the benefit of a full ordinal analysis. A partial remedy is to give canonical assignments for some ordinals (as this paper does). Another partial remedy is to have multiple systems at different strengths each illuminating a different aspect of the theory.

* Even if a notation system is too weak for a theory, setting gaps "as if it were stronger" can sometimes illuminate aspects of the theory.

* If we do not build the notation system in L (or a higher canonical inner model), we get an obstacle to canonicity. For example, ZFC does not prove ω_{1}^{L}<ω_{1}, so an ordinal notation system for ZFC cannot have different terms for ω_{1}^{L} and ω_{1}. It appears that the resolution is existence of multiple natural assignment formulas φ, but they all agree if V=L (or an analog for stronger theories), and therefore if an ordinal has provably the same definition (for example ω_{1}) for natural φ_{1} and φ_{2}, then it gets assigned the same term by both φ_{1} and φ_{2}.

A full completeness (every ordinal has a notation) only occurs in nonstandard models, but perhaps we can have a form of completeness in the true model if we formulate the system as an extensible one. For example, suppose we have a structure with ordinals, and a convention to make every formula φ (alternatively, every φ in a given class) with one-free variable denote an ordinal (for example, let Ord(φ) be the least ordinal satisfying φ, or 0 if there is no such ordinal). Every sound theory T (proving that ordinals are ordered and include 0) gives a c.e. well-founded partial order [φ]_{T} ≤ [ψ]_{T} ⇔ T⊢Ord(φ)≤Ord(ψ). The rank of each formula (in the partial order) is recursive (and worth investigating, but note that some formulas may give definitions that are not canonical for T, and I do not know what the rank of (say) ω_{1}^{CK} is for various T), but the canonical assignment for [φ] uses the actual Ord(φ). If T_{1} ⊂ T_{2} ⊂ T_{3} ⊂ ..., converges to the complete true theory (with each T_{i} c.e.), then at each level, the partial order is c.e., but the limit is the order type of ordinals definable in the structure. An attempt to assign [φ] below Ord(φ) would cause a problem at some T_{n}. Similarly, if we define an ordinal notation system in a sufficiently extensible manner, the canonical assignment is the lowest appropriately definable assignment that does not break the extensibility. (And even if cannot make the above literally true, it acts as a guiding heuristic.)

*What we want from ordinal analysis of a theory T:*

- A canonical formula φ assigning notations to ordinals.

-- Ideal: Every canonically definable ordinal in T gets a notation.

-- Extension: T is consistent with "every ordinal gets assigned a notation by φ". The relative consistency and Π^{1}_{1}-soundness is provable in a weak base theory. T need not prove that if a term is assigned an ordinal, then so do all of its subterms (though it will prove that for every particular numeral).

- A comparison relation '≺' for the system such that provably in a weak base theory (PRA or weaker) '≺' is a polynomial-time computable linear ordering (with a polynomial-time computable domain).

-- Open ended: proof in a weak base system of various basic properties of '≺'.

-- Ideal: '≺' is as simple as possible given the strength of T (except that complexity is sometimes justified by convenience, extensibility, or other goals).

- Proof in T that for all m and n such that φ(m) and φ(n) exist, m≺n ⇔ φ(m) < φ(n).

- Proof in a weak base theory that for all n, T proves that φ(n) exists.

-- Extension (assuming that T is finitely axiomatizable): A proof in T that there is a cut of ℕ such that for k in the cut, φ is total on I_{k} and exists as a set, where I_{k} is the set of notations all of whose subterms are below (using '≺') the kth element of a natural fundamental sequence for '≺'. A further extension is to define φ for notations above an arbitrary (possibly within bounds) ordinal, and with T proving that the above holds for every such ordinal (note that the cut of ℕ can be independent of the ordinal).

- Proof that the supremum of notations for recursive ordinals is the proof theoretical ordinal for T. There are several variations on this, but mainly:

-- Proof in a weak base theory that a Π^{1}_{1} statement is provable in T iff there is n≺Ω such that the statement is provable in a weak base theory plus transfinite induction on ≺ below n. Here, Ω is the notation for the least nonrecursive ordinal. This should be possible for natural T.

-- Extension (if the notation system is given above an arbitrary ordinal *a*): Proof in a weak base theory that a Π^{1}_{2} statement is provable in T iff there is n≺Ω(a) (n uses a placeholder for "a"; Ω(a) is the bound of the recursive part) such that the statement is provable in RCA_{0} plus well-foundedness of the system up to n for every *a*. This applies to typical T that get their Π^{1}_{2} strength using constructs like ∀X ∃Y rather than ∃Y. (While ATR_{0} is needed for basic theory of countable ordinals, a reasonable strong notation system gets ATR_{0} from RCA_{0} (Rathjen 2014).)

- (potentially open-ended) A proof theory for T that corresponds to the ordinal notation system. This includes extending the above to higher definability levels.

- Open ended: A detailed correspondence between fragments of T (and their proof theoretical ordinals) and fragments of the notation system. Part of the assignment being canonical is existence of a natural correspondence between n and the proof theoretical ordinal of (essentially) "φ(n) exists". The correspondence is notation system dependent; φ(n) need not be a recursive ordinal, but the proof ordinal is related to n.

We also want the system to be extensible, both generally, and also as a parameterization of the system achieving a form of completeness (see above and also 4.3 Assignment of Degrees) or at least (to a certain extent) capturing the framework that T intuitively provides for its extensions.

The assignment of ordinals can be viewed not just as a formula but also as a story of the ordinals of T. Even without a proof, a detailed correspondence between the notation system and the canonical ordinals (and set-existence principles) of a theory is strong evidence that the system corresponds to the theory.

In this paper, we define several ordinal notation systems based on the general notion of degree and the corresponding collapsing function C. Key to effective ordinal notation systems is managing complexity and distilling the strength into a simple form. Using C will serve this goal by trivializing syntax (except which forms are standard) and comparison of standard forms while providing a general framework that one can use to achieve arbitrary strength.

**Definition:** Given an arbitrary binary relation on a well-ordered set, which will call a degree (and determine when c has degree *a*), 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.

The *strict version of C* requires that *a* is maximal in C(a,b), with C(a,b) undefined if the least element above b that has a degree *≥a* also has a degree *>a*.

*Notes:*

* 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*.

* The strict version of C is sufficient for standard forms (in the systems we will consider). In this version, existence C(a,b) typically implies that *a* is in some sense built from below from <C(a,b).

* The definition also makes sense for sets that are just linearly ordered.

* A slightly less general presentation (that remains sufficient for us) is that for a well-ordering S, a degree is a partial function f:S→S∪∞, and C(a,b)=min(c>b:f(c)≥a) when such c exists. c has degree *a* iff f(c)≥a. Given a notation system using C (strict version), 0, and Ω (as below), the corresponding choice of f is f(Ω)=∞, f(C(a,b)) = a, and (for definiteness) f(0)=0.

Even at this level of generality, C has the following key properties:

* If *a* is maximal in C(a,b) (and in particular for standard C(a,b)), then C(a,b)<C(c,d) iff C(a,b)≤d ∨ (b<C(c,d) ∧ a<c).

* The order type of terms built using 0 and C is bounded by ε_{0}. Proof sketch: The canonical choice of C here is C(a,b)=b+ω^{a}, and every other choice is essentially a quotient of this choice.

* Consider an arbitrary notation system built using 0 (the least ordinal), Ω (a large ordinal), and C (strict version) with b<Ω ⇒ C(a,b)<Ω.

- The order type of terms above Ω is bounded by ε_{Ω+1}.

- The order type of terms below Ω can be

-- an arbitrarily large recursive ordinal for a recursive system

-- an arbitrarily large countable ordinal for a nonrecursive system

-- an arbitrarily large ordinal <κ^{+} for a nonrecursive system if all ordinals ≤κ (κ<Ω) are added as constants and C(a,b)>κ.

- The comparison of valid terms (terms that we are promised to be valid) is recursive (using the formula above) and independent of the notation system. For the extension above κ, recursive comparison holds given comparison of the constants <κ used in both terms.

- Furthermore, assuming the system always uses C(a, c) in place of C(a,C(b,c)) if b<a (note that these terms are always equal for strict C), then comparison of standard terms is lexicographical if the terms are written in postfix form, with 'C'<0<Ω. For example, C(C(0,Ω),0) would be written as 0Ω0CC, and (assuming standardness) 0ΩC < 0Ω0CC < 0Ω0CC0C < Ω. This also applies to the extension above κ if we use C(a,κ) in place of C(a,b) for b<κ.

To ensure that enough terms are standard (without restricting how strong the system can be), we will only use degrees that are well-behaved as follows.

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

- Every element c∈S has degree 0
_{S}(the least element of S). 0_{S}only has degree 0_{S}. - For a limit
*a*, c has degree*a*iff it has every degree less than*a*. - For a successor
*a*'=*a*+1, either of the following holds:- An element has degree
*a*' iff it is a limit of elements of degree*a*. - There is a limit element d ≤
*a*such that for every c in S, c has degree*a*' iff it has degree*a*and either c ≤ d or c is a limit of elements of degree*a*(or both).

- An element has degree

*Note:* The third condition can be equivalently written as ∀a (C_{a+1} = lim(C_{a}) ∨ ∃d ∈ lim(S)∩(a+1) C_{a+1} = lim(C_{a}) ∪ (C_{a}∩(d+1))), where S is identified with an ordinal (so a+1 consists of ordinals ≤a), C_{a} is the set of elements that have degree *a*, and lim is limit points.

Intuitively, a degree indicates how closed the ordinal is. Degrees are fine-grained in that degree a+1 includes all limit points of the set of ordinals of degree *a*. For typical notions of degrees, the intuitive meaning of c having degree *a* depends not only on how large *a* is but also on the nature of the gap between c and *a*; this is necessary to preserve monotonicity. Given a typical ordinal notation system, the representation of *a* in terms of ordinals <c can be viewed as a reflection configuration with ordinals <c being parameters. Intuitively, if we increase c past certain subterms of *a*, the meaning of these subterms changes from being building blocks of the reflection configuration to that of parameters. Also, not all representations are valid as reflection configurations. Some increases in *a* correspond to diagonalization: We may have an increasing sequence of degrees a_{1},a_{2},...,a_{diag} with c having degree a_{diag} meaning c (if it is not too large relative to a_{diag}) having degree a_{c}. To preserve monotonicity; a_{i} may only be used when i<c. For i≥c, we skip a_{i} by making it equivalent to a_{diag} (and hence to a_{i}+1 and higher degrees <a_{diag}) for c.

Besides C, we might only need 0 and Ω (as above). More generally, however, a *partial ordinal notation system* is a partial mapping O of ordinals into finite sequences of symbols and nonrepresentable ordinals (ordinals not in the domain of O).

**Definition:** For a partial ordinal notation system O and a collapsing function C corresponding to a degree, the standard combination of the notations is defined as follows:

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

Exception: If O includes all ordinals ≤κ as constants, it is often convenient to require that in C(a,b), b≥κ. This helps with embedding notation systems built above different κ.

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 Ω. A well-behaved combined ordinal notation system should satisfy the following (this is not a definition and can be skipped by the reader; the conditions are most relevant when an ordinal notation system is stacked on top of another):

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) < Ω (except possibly when b≥Ω and b+ω^{a} is above all ordinals in the notation system).

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 (C(b,c)) except possibly when c=0 and b is not represented by a C-term.

3. The standard representation of an ordinal is the unique representation using (C and 0) with the least number of C-terms (except that we can have C(a,0)=C(a,b) even if b is not a C-term). This should hold even if all representable ordinals below a particular one were to be added to O as constant symbols.

An example is the notation system below ε_{0} 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}.

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.

More precisely/generally, a notation system above a generic ordinal specifies standardness and comparison given syntactic form and comparison for inputs. For example, pairing gives a notation system for Ω^{2} given a system for Ω, and comparison of (a,b) with (c,d) depends only on how a,b,c,d compare with each other. (Note: While not necessary here, it may be convenient to relax the definition of ordinal notation system above a generic ordinal by allowing comparison with 0 and possibly other queries.) Notation systems in this paper can generally be defined above a generic ordinal. Furthermore, the general form of some constructs is a mapping that given an ordinal notation system above a generic ordinal, turns it into a stronger one. A key value of defining the notation system above a generic ordinal is that it can be used to characterize not just Π^{1}_{1} but Π^{1}_{2} strength of typical theories.

If b < a, then having degree

If 0 < a ≤ b, then

C(a, b) = b+ω

C(a, b) is monotonic in

C(a, b) > b.

If b = C(c, d) where

In general, if

If

*Comparison*:

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 (and standard form) will often involve such comparisons.

We illustrate the framework by defining a notation system at the level of the Bachmann-Howard ordinal, which is the proof ordinal of KP. 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, but only determines which representations are standard. To reach the Bachmann-Howard ordinal, we use the built-from-below condition: define *a* to be maximal in C(a, b) iff its standard representation (equivalently, some representation) in terms of ordinals ≤b (equivalently, ordinals <C(a, b)) only uses ordinals below *a*.

*Intuitive Explanation:* The built-from-below condition intuitively captures the idea of Ω being admissible. A subsystem of the notation system obtained by setting an upper bound on subterms used corresponds to a restriction on the theory and thus to a provably recursive well-ordering. Conversely, the theory corresponds to the union of its restrictions, and the limit/sum of these subsystems corresponds to the proof ordinal (which in a sense, corresponds to ω_{1}^{CK}), and this limit is precisely the order type of built-from-below ordinals. This way, the ability to collapse built-from-below ordinals into ordinals below Ω corresponds to recursive ordinals being below Ω. The above also generalizes to terms built above an ordinal (and for extensions of the notation system, to successor admissible ordinals). Also, ordinal exponentiation above Ω corresponds to quantifiers in induction instances, analogously to PA and ε_{0}.

For C(Ω*a+b, c) (a, b, c < Ω), either Ω*a+b or Ω*(a+1) or Ω^{2} is maximal. C(Ω^{2}, 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 *a*th fixpoint function (ε is the first fixpoint function).

Let H(a, b) is 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

For b < Ω, C(a, b) = H(a, b+1) ∩ Ω = min(c>b: c = H(a,c) ∩ Ω). (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 is Ω 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 = Ω*ω+Γ_{0}*2+1 = C(0, C(Γ_{0}, C(Γ_{0}, C(C(0, Ω), Ω)))), then out of (0, Γ_{0}, Γ_{0}, Γ_{0}, 0), delete the first two and convert the third one to Ω: a → C(, C(, C(Ω, C(C(0, Ω), Ω)))) → C(Ω, C(C(0, Ω), Ω)) = Ω*(ω+1).

To allow more readable ordinal representations, given a definition of C, let us define C_{1} as

C_{1}(a) = C_{1}(a,0)

C_{1}(a,b) = C(a_{1},C(a_{2},... C(a_{n},b)..)) for the least ordinal ω^{an}+...+ω^{a2}+ω^{a1}≥a such that each a_{i} is maximal in C(a_{i},... C(a_{n},b)..).

(Note that the definition is unchanged by requiring a_{n}≥...≥a_{2}≥a_{1}.)

Equivalent definition of C_{1}:

C_{1}(a) = C_{1}(a,0)

C_{1}(0,b) = b

if d < ω^{a+1} and *a* is maximal in C(a,b): C_{1}(ω^{a}+d,b) = C_{1}(d, C(a,b))

if d < ω^{a+1} and *a* is not maximal in C(a,b): C_{1}(ω^{a}+d,b) = C(a,b)

**Notes:**

* The Python module uses "C" in place of 1-variable C_{1}, C(a, base=b) in place of C_{1}(a, b), and "C2" in place of the 2-variable C.

* If one needs two-argument C_{1}, it may be helpful to switch notation so that comparison remains left-to-right. For standard representations, the base b is the more significant term than a.

- C(a
_{1},C(a_{2},... C(a_{n},b)..)) (if each a_{i}is maximal) = C_{1}(ω^{an}+...+ω^{a2}+ω^{a1},b) - C(a, b) = C
_{1}(ω^{a}, b). - If b is fixed, C
_{1}is continuous and monotonic and onto ordinals ≥b. Also, C_{1}is monotonic in b. - If
*a*is not above the least fixpoint of exponentiation base ω above b, then C_{1}(a,b) = b+a. In all cases, C_{1}(a,b) ≤ b+a - If a
_{1}< a_{2}and a_{1}+b is maximal in C_{1}(a_{1}+b,c) and a_{2}is maximal in C_{1}(a_{2},c), then a_{2}+b is maximal C_{1}(a_{2}+b,c). - C
_{1}(a,b) = C_{1}(C_{1}inv(b)+a) where C_{1}inv(b) is the largest x such that C_{1}(x)=b provided that for ∃x b=C_{1}(x).

Formal definitions of ordinal notation systems tend to be simpler using C than C_{1} because C already takes care of addition and exponentiation, while with C_{1}, addition and exponentiation would have to be defined separately. However, C_{1} allows much more readable representations because a single C_{1} can combine a long chain of Cs, and because key properties C_{1}(a) can be read off CNF (for appropriate base) representation of *a*. Also, combining C_{1} with extended CNF (always using the maximum possible fix-point x→ω^{x} as the exponent base) has the benefit that the most significant terms are always to the left, which allows easy comparison.

For example (with C as defined in the Bachmann-Howard Ordinal subsection above):

ε_{ω2+ω+3} = φ(1, ω^{2}+ω+3) = C_{1}(Ω*(ω^{2}+ω+3)) = C(Ω,C(Ω,C(Ω,C(Ω+1,C(Ω+2,0)))))

φ(1,φ(φ(1, ω^{2}+ω+3),5)+6) = C_{1}(Ω^{C1(Ω*(ω2+ω+3))}*4+Ω*6)

As seen above, another key simplification for ordinal representations is that typically C_{1} can be just a one-argument function while two arguments are required for C.

Also, C_{1} allows using integers (including number of repetitions with the same *a*) in binary instead of unary; this shortcut can also be obtained using (for example) C_{n}(i,a,b) = C(a,...,C(a,b)..) (i *a*s; 'n' is a character and not a variable).

The conversion between using C and using C_{1} is straightforward. Typically, in the standard form (and assuming that C_{1}(a) is representable), "C_{1}(a)" is used iff *a* is maximal and there is no other representation of C_{1}(a); in particular, if "C_{1}(a)" is standard, then C_{1}(a) = ω^{C1(a)}. Typically, two-argument C_{1} is not used in standard representations. Comparison of standard forms is based on monotonicity of C_{1} and on C_{1}(a) being a fix-point of exponentiation base ω. For typical C_{1}, assuming that *a* is maximal in C_{1}(a), C_{1}(a+ω^{b}) = ω^{C1(a+ωb)} ⇔ ∃x≤b x=ω^{x} > C_{1}(a).

While the use of degrees allows a simple formalization, it obscures a fundamental symmetry in our notation systems. Namely, every pair (b,a) of representable ordinals defines a special function r(a,b) (with r(a,b)(b) = a) describing how big is *a* relative to b, which can then be applied to other appropriate ordinals.

**Definition:** The *reflection configuration* of a term *a* above b is obtained by

- taking the standard representation of *a* in terms of ordinals/terms ≤b (so subterms ≤b are not parsed for subterms C(c,d)>b),

- in every subterm C(c,d)>b with d<b, replacing d with b

- replacing b with x, and adding λx to the front of the configuration. The variable name x is immaterial as long as x is not used otherwise.

The *constants* used are the outermost subterms <b in the configuration (i.e. a constant (<b) is not parsed for further constants).

The *upper bound* will typically be Ω or infinity, but formally the lesser of the least constant term >b used in the notation system and the term (if any) above all ordinary C-terms.

*Note:* *a* and b can be ordinals or terms in the notation system used. We are not restricting *a* and b provided that *a* has a standard representation in terms of ordinals ≤b.

The notation systems we will define will have the property that if A is a reflection configuration (of *a* above b), and d is an ordinal above the constants used and below the upper bound, then there is unique c such that A is the reflection configuration of c above d. In other words, given *a* and b and d, c is to d what *a* is to b. Furthermore, c is strictly monotonic in *a* and monotonic in d. In general, c will depend on the notation system used. However, if b and d have sufficiently strong reflection properties relative to the notation systems, c will be independent of the notation system, so the differences in notation systems are in how to handle reflection configurations above ordinals without sufficient reflection properties.

A single *a* has a finite set of reflection configurations, with configuration transitions (of the configuration of *a* above b) happening at subterms of *a*. The final reflection configuration of *a* will just use *a* as a constant (i.e. λx.a). In terms of the structure of the systems, reflection configurations can be said to be more important than degrees.

The comparison of configurations is simply the standard comparison with x treated as an ordinal above the constants but below the upper bound. In our systems using C,0,Ω, the lexicographical comparison (of postfix forms) works provided that we are given whether x<Ω (and similarly with other special constants for systems that use them). We will typically only care about configurations for x<Ω, but one can specify it explicitly using λx<Ω. Note that λx.x is the least nonconstant configuration.

*Example:* For the system for the Bachmann-Howard ordinal, the configuration for ε_{0} above any lower ordinal is λx.C(Ω,x), and in line with this value, the least point in the range of ε above b<Ω equals λx.C(Ω,x)(b) = C(Ω,b).

The reflection configuration of *a* above <b is the reflection configuration of *a* above a sufficiently large term <b, except that for nonlimit b, we treat it as the configuration above an imaginary ordinal above all of b's predecessors. Thus, the only difference with using '<' is when *b* is a subterm of *a*.

Of particular importance is the reflection configuration of *a* above C(a,b) (standard term). If the configuration is λx.A(x), the configuration of C(a,b) above <C(a,b) is λx.C(A(x),x), which characterizes how big/reflective C(a,b) is relative to lower ordinals. Note that both configurations are also valid above every x<C(a,b) that is above all outermost subterms of C(a,b) that are <C(a,b).

*Note on testing for standard forms:* If a condition for standardness relies on the configuration of *a* above C(a,b), then in testing it, use standard comparison to determine which terms are <C(a,b). Then apply the condition to check for standardness. For example, C(C(Ω,0),0) is only standard if C(C(Ω,0),0) < C(Ω,0), so the configuration to check (for a=C(Ω,0)) is λx.C(Ω,x) rather than λx.C(Ω,0).

**Notations related to reflection configurations**

To avoid repeating ourselves, here are some notations that make defining particular systems easier. The reader is free to skip this part and come back when encountering a definition that uses reflection configurations.

In testing C(a,b) for standardness with *a* and b standard and b minimal, the remaining condition is about *a*.

* T_{a} is the subterm/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 x is a proper subterm of y. Identical terms at different positions are distinguished (in the quantifiers and in ⊏).

*Note:* T_{a} will be useful in stating the conditions in first order logic.

* d=parent(c) means c⊏d ∧ ¬∃e c⊏e⊏d, but as a special case, parent(a) is C(a,b).

* d=parent_{<Ω}(c) means c⊏d ∧ d<Ω ∧ ∀e (c⊏e⊏d) e≥Ω, or if there is no such d, parent_{<Ω}(c) is C(a,b). In other words, if ordinals ≥Ω are merely syntactic constructs, d is the real parent of c.

* r(c,d) is the reflection configuration of c above d.

* r(c) is r(c,parent(c)), annotated with the position of c inside Ω; the standard comparison is used for C(a,b) even if it is nonstandard.

* r_{<Ω}(c) is as above using r(c,parent_{<Ω}(c)).

*Note:* r(c) or (as appropriate) r_{<Ω}(c) are the relevant configurations for extending built-from-below to reflection configurations.

* d∈r(c) iff d⊑c ∧ ∀z (d⊏z⊑c) z≥parent(c) (and similarly with r_{<Ω}(c); the point is that r(c) uses d, possibly as a leaf term)

* r(e)⊆r(c) iff ∀z (z∈r(e)⇒z∈r(c))

For a reflection configuration *a*, the subterm tree T_{a} is defined as if it were an ordinal, except that the constants <x are not parsed further. r is defined as above (without fallback to C(a,b)) by replacing x with a fictious (sufficiently large below the upper bound) ordinal x_{0}, computing the configuration, and replacing λx with λx_{0} λx. If a configuration already uses λx_{0}, then use x_{1} (like x_{0}), and replace λx_{0} λx with λx_{0} λx_{1} λx; and so on. The comparison remains standard (lexicographical in postfix form with (if x<Ω) C < 0 < x_{0} < x_{1} < x_{2} < ... < x < Ω). For x<Ω, r_{<Ω} is defined analogously.

Comparison between configurations for x<Ω and x≥Ω is by default undefined. However, in our systems using C,0,Ω it will be convenient to compare them as follows: For the configuration for x<Ω, replace Ω with Ω' (except in the constants below x) and then use the usual (lexicographical for postfix forms) comparison with C < 0 < Ω < x < Ω' (actually, any use of Ω' will make the configuration greater). For example, λx<Ω.5 = λx≥Ω.5 < λx>Ω2.Ω2 < λx<Ω.x < λx<Ω.Ω. See 4.4 A Step towards Second Order Arithmetic for an extenson of this for certain systems.

In this section, we define an ordinal notation system for rudimentary set theory plus "for every ordinal *a*, there is recursively *a*-inaccessible ordinal". Instead of rudimentary set theory, we can use a stronger theory like Π^{1}_{1}-CA_{0}.

*Note on rudimentary set theory:* Rudimentary set theory consists of extensionality, foundation, empty set, and closure under rudimentary functions (as a schema, or using a selected set of rudimentary functions). Assuming infinity, it is conservative over ACA_{0}, but it is more general in that it does not assume countability, and (in the other direction) handles sets without assuming ATR_{0}. Every level of the Jensen hierarchy for L satisfies rudimentary set theory, and conversely it can be used to define L and be the basis of a natural axiomatization of J_{a}. Outside of L, the theory is too incomplete to fully function as set theory, but one possible remedy (assuming choice but remaining conservative over ACA_{0}) is to require that every set S is in L[X] for some X⊂ω_{α} where X depends on S, and ω_{α} is the cardinality in the transitive closure of S (assuming the closure is infinite).

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

- C(a, b, c) is the least ordinal
*e*of admissibility degree*a*that is above*c*and is not in H(b, e). - 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. - 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 admissibility 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 Definition of the General Notation subsection.

A polynomial time comparison algorithm is obtained as follows:

- In C(a, b, c), treat (a, b) like an ordinal and use the comparison relation in the Definition of the General Notation subsection. 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) ∧ (a, b) < (c, d).

Note: (a, b) < (c, d) iff a < c, or a = c and b < d. *a*is always maximal in C(a, b, c).*b*is maximal in e = C(a, b, c) iff b is in H(b, e).*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.

C(0, x) = x+1,

C(b, c) = H(b, c+1) ∩ c

C(b, c) is the least ordinal not in H(b, c+1).

However, C(1, 0

C(b, c) = min(c+ω

C(a

{x: c < x < C(a, b, c) and

C(a, C(a+1, 0, b), b) is the least ordinal

C((0

C((0

C(0

C(C(1, 1, 0), 0) is the proof-theoretical ordinal of Π

C(C(1, 1, 0)

C(C(2, 0, 0), 0) is the ordinal for Π

C(C(2, 0, 0)

C(C(3, 0, 0)

In this section, we present an ordinal notation system for KP + {Π_{n} reflection}_{n}, which should have the same strength as ACA_{0} + lightface Π^{1}_{2} comprehension. The version using Veblen Normal Form reaches beyond existence of κ^{+}-stable κ.

**Definition:**

**Syntax:** 0 (the least ordinal), C (binary function), Ω (large ordinal), **O**.

**Condition for O:** **O** is a notation system for ordinals >Ω in terms of ordinals <Ω. Ordinals <Ω are treated as given in **O**: Comparison and validity of **O**-terms depends only on the term structure and on comparison of the ordinals <Ω used by the terms.

**Definition of C:** 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. C is as given in "A Framework for Ordinal Notations". This fully specifies the system (if we do not use gaps) apart from maximality of *a*. *a* is maximal in C(a, b) iff for every ordinal d in the **O** representation of *a* (d<Ω), 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.)

**Canonical choice of O:** For definiteness, let **O** be Cantor Normal Form base Ω. Other choices include C with C(a, b) = b + ω^{a} (b ≥ Ω; in the standard form b = Ω or b ≥ max(ω^{a}, Ω)), or for a stronger system, Veblen Normal Form.

**Notes:**

* For a more explicit phrasing, see Comparison Algorithm below.

* When C is used for **O**, the system is superficially similar to (but weaker than) the n=2 notation system in 5 Main Ordinal Notation System.

* A natural strengthening is 8.2 Degrees of Reflection with Passthrough.

* Compared to using C, using CNF base Ω has the same strength but allows additional terms. For example, if a = Ω+d with d = d_{1}+...+d_{n} <Ω (each d_{i} is additively indecomposable and (d_{i}:1≤i≤n) is nonincreasing), we only check d rather than checking the representation of each d_{i} for ordinals >d_{i}. However, if the representation of *a* using CNF base Ω does not use ordinals >C(a,b) that are not fix-points of x→ω^{x}, then C(a,b) is the same in both systems (but converting C(a,b) still requires conversion of *a* and b).

**Comparison Algorithm**

Here, we explicitly state the comparison algorithm and the conversion to the standard form (when C is used for **O**).

**Syntax:** Two constants (0, Ω) and a binary function C.

**Comparison:** For ordinals in the standard representation written in the postfix form, the comparison is done in the lexicographical order where 'C' < '0' < 'Ω': For example, C(C(0,0),0) < C(Ω,0) because 000CC < 0ΩC.

**Standard Form:**

0, Ω are standard

"C(a, b)" is standard iff

1. "a" and "b" are standard,

2. b is 0 or Ω or "C(c, d)" with a≤c, and

3. ∀x∈T_{a} ∀y⊏x (x<y<Ω) ∃z⊒y (z<Ω) (z⊐x ∨ z < C(a, b)).

Here T_{a} is 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 x is a proper subterm of y; identical terms at different positions are distinguished (in the quantifiers and in ⊏).

Note that ∃z⊒y (z<Ω) z⊐x simply means that x is not in the representation of *a* in terms of ordinals <Ω (with z⊒y redundant).

**Note:** The '<' uses the above-described lexicographical order (including for z < C(a, b)).

*When using an arbitrary O for ordinals >Ω:* Condition (3) applies verbatim. (The term structure above Ω is irrelevant as long as the ordinals used <Ω are unaffected.) The other conditions are standard for C and can be handled accordingly. (In condition (2), exclude b=Ω. Use standard comparison for C. Comparison and standardness of

*Conversion of nonstandard forms:* To convert 'C(a, b)' to the standard form (when C is used for **O**), first convert 'a' and 'b'. Next, recursively minimize b by replacing it with d for as long as b is C(c, d) and c<a. If we are not done, then perform a right-to-left (with functions written in prefix form) preorder traversal of T_{a} until we find the first *y* that violates the above condition. Replace *y* with Ω, and delete everything in 'a' to the left of 'y' (except for the required number of 'C'). Convert 'a' to the standard form. 'C(a, b)' is now a standard representation.

**Examples**

Here are examples using a canonical **O**, and setting gaps in the canonical way.

C(Ω*a+b, c) = C(a, b, c) of the previous notation (for a, b, c representable in that notation; **O** uses CNF base Ω).

Ordinals (below Ω and with a<Ω) of degree Ω^{a+1} are recursively *a*-Mahlo ordinals (and their limits), except that if c=C(Ω^{a+1},b)≤a, c is recursively c-Mahlo.

C(C(Ω, C(Ω^{2}, 0)), 0) is the ordinal for KPM (KP + the universe is recursively Mahlo).

In general, for many appropriate conditions F (including Π_{n} reflection), 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(Ω^{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.

Ordinals below Ω of degree Ω^{Ω} are Π_{3} reflecting ordinals (and their limits).

Ordinals below Ω of degree Ω^{ΩΩ} are Π_{4} reflecting ordinals (and their limits), and similarly with Π_{n} reflection.

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 analogous property holds for ordinals of degree a*b and Π_{2} reflection. For example, C(Ω^{ΩΩ+Ω+1},0) is the least ordinal that is Π_{2} reflecting onto Π_{3} reflecting ordinals that are Π_{2} reflecting onto Π_{4} reflecting ordinals.

Similarly, C(Ω^{ΩΩΩ+Ω+1},0) is the least ordinal that is Π_{3} reflecting onto Π_{4} reflecting ordinals that are Π_{3} reflecting onto Π_{5} reflecting ordinals, and similarly for Π_{n} reflection.

*Levels of Stability (using Veblen normal form for O)*:

C(Ω

C(ε

C(φ

C(φ

*

* If one extends

* It is unclear whether for non-Gandy α<Ω, C(Ω, α) should canonically be α

**Additional Properties**

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 ordinal above ω and below Ω in the notation is admissible iff its maximum degree has effective cofinality Ω using **O** (with effective cofinality of Ω being Ω); equivalently iff it is a limit ordinal and every increasing sequence of ordinals in the notation system having that ordinal as a limit uses arbitrarily high ordinals up to the limit of **O** in the representation of the 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 ε_{0}. 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). Another possibility is to use such *a* to fill in the gaps in the notation.

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 (in a well-founded system, the order type using **O** and ordinals <a (given a<Ω and not counting ordinals ≥Ω) must be <Ω).

As noted previously, using C_{1} rather than C can improve readability. Here is an example using C_{1}:

C_{1}(Ω^{ΩΩ}+Ω^{Ω2}*3+Ω^{Ω}*4+Ω^{2}*5+Ω*6) is the 6th admissible ordinal after the 5th recursively inaccessible ordinal after the 4th recursively-Mahlo ordinal after the 3rd recursively hyper-Mahlo ordinal after the 1st Π_{3} reflecting ordinal.

In C_{1}(...+Ω^{a}*b+...), Ω^{a}+b corresponds to going up by b (b is count) a-recursively inaccessible ordinals and their limits; if b is above the result, it encodes how much diagonalization to take (and similarly with other ordinals above the result). If a = ...+Ω^{c}*d+..., c encodes degree of recursive Mahloness and d encodes the number of times to take a limit operation where at successor steps the limits must correspond to c (where c encodes degree of recursive Mahloness). For example, a=Ω^{2}+Ω*2 corresponds to recursively Mahlo limit of recursively Mahlo limits of recursively hyper-Mahlo ordinals. Limit values of a,b,c,d are handled using the limiting process; for example C_{1}(Ω^{Ωω}) is the least limit of recursively n-Mahlo ordinals for all finite n (and hence is not admissible).

A natural extension of the system with the same strength is to use C_{1} instead of C in representing ordinals <Ω that are fix-points of x→ω^{x}. For example, in testing for standard form, in C_{1}(Ω+d), d<Ω would be parsed for ordinals >d that are below Ω and not in the scope of an ordinal <C_{1}(Ω+d).

In this section, we present the conjectured canonical assignment of notations to ordinals. We assume that **O** uses CNF base Ω for **O**, or is or extends Veblen normal form (with exponentiation base Ω). Note that the does not prevent an arbitrarily strong **O**.

In its most general form, given a sufficiently strong **O** for an appropriate theory T, the assignment can be used to represent canonical ordinals for T between an ordinal *a* (at least for *a* below non-Gandy ordinals or otherwise avoiding them) and the least Σ^{1}_{1}-reflecting ordinal >a. Such **O** would typically correspond to the proof ordinal of T. For weaker **O**, we get up to iterations of Π^{1}_{1}-reflection that are within **O**. The assignment works above an arbitrary ordinal *a*, using lower ordinals as constants, and allows choosing representations such that we need not worry about comparison of C-terms below *a*. For non-Gandy *a*, the definition works, but likely misses some canonical ordinals.

In formulating the assignment, our goal is that for appropriate T ranging from Π^{1}_{1}-CA_{0} (or less) to (beyond) KP + ∀α ∃(κ^{+}-stable κ>α)), T + "every ordinal is assigned a term" is Π^{1}_{1} conservative over T. For stronger theories using a stronger **O**, this should apply to every ordinal in the interval we cover. So our assignment has to work even in appropriate T too weak to prove well-foundedness, and we cannot require closure under subterms (consistently with T, a collapse of a fictitious ordinal might be well-founded).

**General Framework**

The assignment of ordinals assumes that the notation system has gaps; otherwise, all ordinals would be recursive; in the canonical assignment, gaps are set in the canonical way. Pick any sufficiently closed ordinal Ω, say the least Σ^{1}_{1}-reflecting ordinal above the ordinals of interest (if building a notation system above an ordinal). For a simple suboptimal variation (or for the suboptimal old version), if using C or CNF base Ω for **O**, it suffices that Ω is ε_{Ω++1}-stable, and Ω^{++}-stable should suffice for reasonable **O**. Alternatively, treat Ω as a syntactic construct and treat an ordinal ≥Ω either syntactically or as a pair (Ω, ordinal using Ω). We will define C(a,b) when *a* is representable using ordinals <C(a,b) as constants. This suffices for the system and allows extensions. In the system using C or CNF base Ω for **O**, the least non-representable ordinal is C(C(ε_{Ω+1},0),0); also, note that if b≥Ω, C(a,b)=b+ω^{a}.

C(a,b) is the least ordinal above b that has degree *a*. Thus, it suffices to define degrees. A complication to recursively defining degrees is that notations can use higher ordinals for which degrees have not yet been constructed. We work around this by defining when:

x has degree d where d is a term that uses C, **O**, and ordinals <x as constants.

The recursion will assume that degrees for ordinals <x have been constructed. Therefore, (using standard comparison for C from "A Framework for Ordinal Notations" and the criterion for maximality of *a* in C(a,b)) we have comparison for terms that use C, **O**, and ordinals <x as constants (except possibly in weak theories). In turn, the degree of x lets us compute whether C(a,b)>x. Also, note that degree d makes sense for all ordinals y<x where y is above all constants used in d.

Every ordinal has degree 0. Assume that x is limit; otherwise x only has degree 0. Let us say that a degree (or (defined below) n-degree) d is <x maximal if for all sufficiently large y<x, d is maximal in C(d, y) (so C(d+1,y) > C(d,y)) (equivalently if there is y<x such that y is above all ordinals <x included in d and d is maximal in C(d, y)).

If we are promised that every C(a',b')≥x, then verification of <x maximality and comparison of such degrees is standard, depending only on comparison of constants <x. Also, <x maximality is defined/tested without referencing ordinals above x. For weak theories, we need an additional trick. Instead of using a single notation for d, in C(a',b') (b'<x) we can allow arbitrary b'<x that are at least as large as the standard choice (and referencing d only needs a single representative). We will use this to depend only on ordinals close enough to x. Moreover, if all b'<x (in C(..,b')) are identical, then the required testing for C(a',b')≥x depends only on the degree of x (with lower degrees permitting more forms, so underestimating a degree does not invalidate verification of having it, and the construction should work).

Note the similarity with 2.5 Reflection Configurations since a degree gives a lower bound on the configuration of x above <x (if it exists).

x has degree d iff has x has <x-maximal degree d'≥d. (This holds because d does not use ordinals that are not representable from <x.) From now on, we mostly focus on <x-maximal degrees. In "x has <x-maximal d if ..", we assume that d is <x-maximal.

x has <x-maximal degree d+1 iff x is a limit of ordinals of degree d. This implies that x has degree d+1 iff x has degree d and (1) x is a limit of ordinals of degree d or (2) d is not <x maximal.

If d is a limit and the **O**-cofinality of d is <Ω, then x has degree d iff it has every degree <d.

*Notes:*

* The cofinality is required to be <Ω because our notation system has gaps.

* Weak theories typically will not prove that degrees <d are well-founded. However, the operative conditions for successor and **O**-cofinality Ω <x-maximal d' are phrased in terms of lower ordinals, which prevents infinite regress. An equivalent explicit definition for <x-maximal d (not of **O**-cofinality Ω) is that there are arbitrarily high d'<d such that x is a limit of ordinals of degree d'.

**Cofinality Ω (using CNF base Ω)**

If d has cofinality Ω in **O** (using CNF base Ω for **O**), separate out the rightmost 1 using CNF base Ω of d, and let n be its height (with the base being at height 1). Thus, n=2 for ..+Ω^{..+1} (including ..+Ω^{1}), and n=3 for ..+Ω^{..+Ω..+1}, and so on.

x has degree d iff it has n-degree d or is a limit of such ordinals. n-degree is based on Π_{n} reflection (and 1-degree is just degree), with the numbering of degrees chosen to be consistent between different n.

An ordinal x has n-degree e+Ω^Ω^..^Ω (using n-1 Ω; using CNF; <x maximal degree) iff it is a Π_{n} reflecting limit of ordinals of degree e. (Also, this is a special case of the next sentence since "Π_{1}-reflecting on" is the same as "limit of", except that only here do we allow e=0.)

More generally, x has n-degree ..(e+Ω^Ω^..^1) (using CNF; <x maximal degree) where the 1 is at height n and the '+' is at height m iff x is Π_{n} reflecting and is Π_{m} reflecting onto ..(e).

If f = ..(e) has **O**-cofinality Ω, Π_{m} reflecting onto f means x is Π_{m} reflecting onto ordinals of n'-degree f, where n' is the height of the rightmost 1 in f.

Otherwise, it means there are arbitrarily large <x-maximal g<f with **O**-cofinality Ω such that x is Π_{m} reflecting onto g, with n' (the height of the rightmost 1 in g) is ≥m.

**Levels of Stability**

The above analysis also applies to a-stable x for a<x. We will use Veblen normal form base Ω, for convenience using φ_{a}(b) for Veblen φ_{a}(Ω+b) (a<Ω), and φ_{0}(b) for Ω^{b}.

The height of the rightmost '1' in d = ..+φ_{a1}(..+φ_{a2}(...+φ_{an}(..+1))..) (with a_{i}<Ω) is ω^{a1}+ω^{a2}+...+ω^{an}, but with 1 added if finite, and 1 subtracted (on the right) if the '1' is in a subterm of the form φ_{a}(Ω^{1}) or φ_{a}(..+Ω^{1}) (a>0 in both forms). (Note that ordinals like ε_{Ω+1} do not have cofinality Ω.) The height of the rightmost '+' (above) is determined the same way, but without the subtraction.

Going further, the least κ-stable κ is C(φ_{φΩ(1)}(1)) (with φ as above). Diagonalization presents additional complications, but up to κ^{+}, we can address them as follows. The height (of '1' and '+' above) will still use ω^{a1}+ω^{a2}+...+ω^{an} (adjusted as above), but a_{i} might be above x, in which case a_{i} is converted into the order type of {h<a_{i}: h is <x-maximal}. (Also, in a weak theory, if this is ill-founded, we give up setting this degree, except through higher degrees.) Further still, Π_{Ω} reflection corresponds to κ being κ^{+}-stable (and to Π^{1}_{1}-reflection).

*Notes on transfinite reflection levels*:

* For a>0, Π_{ω*a} reflecting means a-stable, and Π_{ω*a+n} reflection of x is defined using reflection of L_{x+a} onto an ordinal below x for the appropriate set of formulas. The definition for reflection onto a class of ordinals is analogous.

* Alternatively, transfinite Π_{a} reflection (for a<x) can be defined using infinitary formulas (with the set coding the formula in L_{x}). Note that every Π_{a} formula for limit *a* is Π_{a'} for some a'<a.

* If *a* is an x-recursive well-ordering (potentially ≥x), Π_{a} reflection can also be defined using almost self-referential formulas, with ψ(c,x) (c∈a), allowed to use ψ(c',y) with c'<c as a subformula (except that if c+ω>a, we have to count the quantifiers to confirm that the depth is ≤a).

**Iterations of Π ^{1}_{1}-reflection**

Starting with Π^{1}_{1}-reflection, the picture changes qualitatively because Π^{1}_{1}-reflection for κ can be iterated up to (informally) κ^{++} times as opposed to up to κ^{+} times for lower reflection levels, and iterations of the reflection capture the notation system. Essentially, ordinals <κ^{+} can be used freely, because if a and b are two different recursive representations of α above κ (using constants <λ), then above λ<κ, that a and b denote the same ordinal is Π^{1}_{1} and can be added as a reflection condition, so it does not matter whether the reflection is iterated along a or b. Now given an ordinal notation system **O** above a generic ordinal, interpret **O** above κ^{+}, and given an **O**-term A>0, Ath iteration of Π^{1}_{1}-reflection means being Π^{1}_{1}-reflecting onto Bth iteration for every B<A, with the 1st iteration simply means being Π^{1}_{1}-reflecting, or (as appropriate) Π^{1}_{1}-reflecting onto a given set.

Now, in the notation system (with x being Π^{1}_{1}-reflecting), parse the rightmost term of d until reaching either φ_{Ω}(a) (a>0) or a=φ_{Ω}(a)>Ω. Collapse the terms (<Ω) in **O** representation of *a* into ordinals below x^{+} using a_{i} → order type of {h<a_{i}: h is <x-maximal}, and convert a into a' using **O** above x^{+}. Subtract 1 from a' (and store the result as a') if a' was b+n where n is finite and b is limit with **O**-cofinality <x^{+}. Now, having <x-maximal degree d means being a'-Π^{1}_{1}-reflecting and also being Π_{m} reflecting onto ..(e) (or is a limit of such ordinals), where m and ..(e) are as above (see "Cofinality Ω (using CNF base Ω)" and its application to levels of stability; the rightmost '+' considered must be outside of a, so m<Ω).

Note that we do not require **O** to be well-founded, and d having **O** cofinality Ω is equivalent to every converging (to d) sequence having ordinals/terms unbounded in Ω. Assuming we have not missed anything, by plugging in appropriate **O**, we get the complete assignment below the least Σ^{1}_{1}-reflecting ordinal even in strong theories. For a sufficiently closed appropriate theory (such as Z_{2}), **O** would correspond to its proof-ordinal built above a generic ordinal, which might be available from other systems in the paper. Also, by using order-preserving bijections, the canonical assignment also applies to other appropriate ordinal notation systems.

*A simple suboptimal assignment:* There is also a relatively simple suboptimal assignment (that might not work in weak base theories) that should have the right limit when using Veblen normal form. As above, let e-Π^{1}_{1} reflecting mean e-fold iteration of being Π^{1}_{1}-reflecting. C(0,x) will be the next admissible ordinal above x. x has <x maximal degree f iff x is f'-Π^{1}_{1} reflecting (or even simpler, but with the wrong limit, f'-stable), or is a limit of such ordinals, where f' is roughly analogous to the old version below. Specifically, let f_{1} be the order type of {h < f : h is <x maximal }. Let y be the order type of representable ordinals below C(Ω, x) (allowing x and ordinals <x as constants). Express f_{1} using **O** base y and then change to **O** base x^{+} (the least admissible ordinal above x) to get f'.

**Old Version**

*Notes:*

* The text branches from the main text starting with "Cofinality Ω (using CNF base Ω)".

* The assignment below is retained for historical purposes but it misses some canonical ordinals starting with the least Π_{3} reflecting ordinal that is Π_{2} reflecting onto Π_{3} reflecting ordinals, which leads it use higher ordinals (for given terms) than the canonical assignment. The canonical assignment only uses ordinals through Π_{n} reflection. I would like to thank a reviewer with alias Hyp cos for pointing out the issue (in a related system) and suggesting the right strengths, which was instrumental in getting the new version above.

Otherwise, the fundamental sequence for d using CNF base Ω has length Ω and d is <x maximal. d has the form e + Ω^{f} (additive decomposition) where f is successor or is ≥Ω. x has degree d iff x has admissibility degree f' and is a limit of ordinals of degree e, or a limit of such ordinals (that is a limit of ordinals of admissibility degree f' that are limits of ordinals of degree e), where f' is such that f_{deg}(f')=Ω^{f} (so f' is f or f-1; f_{deg} is defined below). This reduces assignment of degrees (below ε_{Ω+1}) to that of admissibility degrees. (Note: The notion of admissibility degrees used here corresponds to degrees of recursive Mahloness and beyond and not degrees of recursive inaccessibility.)

We now define admissibility degrees when the admissibility degree d is <ε_{Ω+1}, which suffices for the notation system. Every ordinal has admissibility degree 0. Let f_{deg} be the function converting admissibility degrees to degrees: f_{deg}(d) = Ω^{d}, except that if d is a limit with fundamental sequence (using CNF base Ω) shorter than Ω, or if d is such a limit plus a finite ordinal, then f_{deg}(d)=Ω^{d+1}. d has the form (CNF base Ω) e + Ω^{f}*g. x has admissibility degree d iff

Case A: f_{deg}(d) is not <x maximal. x has admissibility degree d' for the least d'>d such that f_{deg}(d') is <x maximal.

Case B: g is limit and f_{deg}(d) is <x maximal. x has admissibility degree e + Ω^{f}*h for every representable h<g (equivalently, for cofinally many h<g).

Case C: g is successor and f_{deg}(d) is <x maximal. x is Π_{2+f'} reflecting onto ordinals of admissibility degree e + Ω^{f}*(g-1) (g-1 is the predecessor of g) where f' is derived from f as follows:

- Let f_{1} be the order type of {h: f_{deg}(e + Ω^{f}*(g-1)+Ω^{h}) is <x maximal and h is a representable ordinal <f} (so f' = f_{1} = f if f≤x)

- Let y be the order type of representable ordinals below C(Ω, x). Express f_{1} using CNF base y and then change CNF to base x^{+} (the least admissible ordinal above x) to get f' (so f' = f_{1} if f<Ω).

If the notation system is restricted to terms below Ω^{Ω}, the assignment of gaps simplifies as follows: c = C(a,b) is the least ordinal consistent with its degree of recursive Mahloness and assignment of notations below c (here, the system is simultaneously built above all ordinals; the least notation incorrectly assigned would be C(Ω^{C(ΩΩ, 0)+2}, 0)). For every ordinal c=C(a,b) representable using lower ordinals as constants (even without the restriction on terms), c is admissible iff CNF base Ω fundamental sequence of *a* has length Ω, and c is recursively f-Mahlo iff it is admissible and *a* is of the form ...+Ω^{d}*e (CNF base Ω) where d>f and f≤a; recursively 0-Mahlo means admissible.

The notation system below is only slightly more powerful, yet by introducing the idea of "correctness", it arguably 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. Thus, while retained for historical purposs, the specific system here is essentially superceded by the main system. However, the "Levels of Correctness" part applies generally (including to the main notation system).

**Levels of Correctness**

In the above system (Degrees of Reflection), the reflection properties of C(a,b) (b<Ω) change qualitatively as *a* crosses Ω, and Ω itself (corresponding to Ω_{2} below) is qualitatively different. To reach second order arithmetic, we need ω levels like this (corresponding to Σ_{n} correctness), which we abstract into the following general definition of correctness.

*Definition:* Let C be as in the General Notation. Let us say that a definition of correctness is compatible with C iff:

* Every ordinal has correctness 0; 0 only has correctness 0.

* The set of ordinals of correctness i is closed (i∈ℕ).

* If i<j, then correctness j implies correctness i.

* If i<j, the least ordinal above an ordinal b of correctness i is below the least such of correctness j. However, it is permitted that such ordinals are above all representable ordinals, and to define correctness only for representable ordinals.

* C(a,b) has correctness i>0 iff there is c with correctness i+1 with b<c≤a.

* If a is the least ordinal of correctness i above b, then C(a,b) < C(a+1,b).

For a notation system, let us use C, 0, Ω_{i} (0<i<ω), with Ω_{i} being the least ordinal of correctness i. At this point (if we do not use gaps), despite its generality, C(a,b) is fixed apart from when *a* is maximal in C(a,b). Moreover, if using the strict version of C, the comparison of valid terms is independent of the notation system, and so is the determination of the correctness level of a valid term. For standard form, consistent with the main notation system below, we can use minimal b in C(a,b) and Ω_{i} in place of C(Ω_{i+1},0).

*Properties of the system*:

The least ordinal of correctness i>0 above b, Ω_{i}(b) = f^{(n-i)}(Ω_{n}) whenever i≤n and Ω_{n}>b and f(x)=C(x, b).

0 < Ω_{1} < Ω_{2} < …

C(a, b) < Ω_{i} iff b < Ω_{i} and a < Ω_{i+1}.

C(a, b) = Ω_{i} iff b < Ω_{i} and a = Ω_{i+1}.

Ω_{i} is always maximal in C(Ω_{i}, b) (and as always, 0 is maximal in C(0, b).

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. (Also, infinite correctness level can only occur in extensions of the system.)

*Reflection configurations:* (See 2.5 Reflection Configurations for definition.) Let Ω_{i}(x) denote the least ordinal of correctness i above x. When defining a reflection configuration above b (or above <b), a reasonable notation is to replace Ω_{i}>b (or Ω_{i}≥b respectively) with Ω_{i}(x). This way, all reflection configurations are valid without an upper bound (unless we use a definition that breaks them), and we do not have to specify the domain explicitly. The comparison of configurations is lexicographical (in postfix form) after converting everything to the same Ω_{i}(0) and Ω_{i}(x) using Ω_{j}(x) = C(Ω_{j+1}(x),x). In this notation, λx.Ω_{1}(x) > λx.Ω_{2}(0), and the latter configuration is only valid for x>Ω_{2} (and 0 serves to avoid confusion).

**A Particular System**

Using the above template, let us define a system analogously to Degrees of Reflection, but with an additional built-from-below condition to ensure well-foundedness.

*Definition of the system:* 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 algorithm for checking whether a particular representation is standard, and I expect there is also a polynomial time algorithm for converting arbitrary C-terms to the standard form.

For the conjectured canonical assignment:

Every ordinal has correctness 0.

An ordinal *a* has correctness 1 if it is admissible >ω (or a limit of such ordinals).

An ordinal *a* has correctness of n+1 (n>0) if it is a Σ^{1}_{1}-reflecting limit of ordinals of correctness n (or a limit of such ordinals).

*Note:*

A more natural assignment of correctness (corresponding to second order arithmetic) is given in the next section.

The notation system is conjectured to reach 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 Π^{1}_{1}-CA_{0} + lightface Π^{1}_{2} comprehension. I have not ruled out that due to non-Gandy ordinals, the assignments should be lowered.

**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}^{2}, 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.

** Definition:** An ordinal *a* is 0-built from below from <b iff *a*<b

*a* is n+1-built from below from <b iff the standard representation of *a* does not use ordinals above *a* except in the scope of an ordinal n-built from below from <b.

(Note: "in the scope of" means "as a subterm of".)

The n^{th} (n is a positive integer) ordinal notation system is defined as follows.

**Syntax:** Two constants (0, Ω_{n}) and a binary function C.

**Comparison:** For ordinals in the standard representation written in the postfix form, the comparison is done in the lexicographical order where 'C' < '0' < 'Ω_{n}': For example, C(C(0,0),0) < C(Ω_{n},0) because 000CC < 0Ω_{n}C.

**Standard Form:**

0, Ω_{n} are standard

"C(a, b)" is standard iff

1. "a" and "b" are standard,

2. b is 0 or Ω_{n} or "C(c, d)" with a≤c, and

3. *a* is n-built from below from <C(a,b) (use standard comparison to check).

**Notes:**

* For basic properties, see 2 A Framework for Ordinal Notations above. For example, C(a,b) = b+ω^{a} for *a* below the least ε_{x}>b.

* For b < Ω_{n}, note that Ω_{n} is 1-built from below from b but not 0 built from below from b.

* A variation is to require *a* to be n-built from below from ≤b, which would simplify the definition a bit but lead to arbitrary restrictions like disallowing C(a,b) for a=Ω_{2}+C(Ω_{2}*2+**C(C(Ω _{2}*3,0),0)**,0) and b=0 (the highlighted term is between b and C(a,b)).

*

For n=0, this system just reaches ε_{1}, for n=1, this is the notation system for 2.3 Bachmann-Howard ordinal given earlier, and for n=2, the notation system is superficially similar to (but perhaps much stronger than) the one in 4 Degrees of Reflection. A natural conjecture (see 5.2 Strength of the Main System) that the strength of the n^{th} ordinal notation system is between Π^{1}_{n-1}-CA and Π^{1}_{n}-CA_{0} (or higher), and thus the sum of the order types of these ordinal notation systems is the proof-theoretical ordinal of second order arithmetic (or higher).

**Combined System:** The ordinal notation systems are best combined into one system as follows:

Constants 0 and Ω_{i} (for every positive integer i), and binary function C.

Ω_{i} = C(Ω_{i+1}, 0) and the standard form always uses Ω_{i} instead of C(Ω_{i+1}, 0).

To check for standard form and compare ordinals use Ω_{i} = C(Ω_{i+1}, 0) to convert each Ω to Ω_{n} for a single positive integer n (it does not matter which n) and then use the n^{th} ordinal notation system.

**Nonstandard forms: ** To make C a total function for *a* and *b* in the notation system, let C(a, b) be the least ordinal of degree ≥a above b, where the degree of Ω_{i} is Ω_{i+1} and the degree of C(c,d) is c if "C(c,d)" is the standard form. I believe that this is recursive with the conversion to standard form as follows.

**Conjectured conversion to the standard form for the n ^{th} notation system:** To convert 'C(a, b)' to the standard form, first convert 'a' and 'b'. Next, recursively minimize b by replacing it with d for as long as b is C(c, d) and c<a. If

**Proposition:** In the *n*th system, given a standard term *a* (in prefix form), every nonempty suffix of *a* augmented with the corresponding number of 'C' on the left is standard.

*Note:* For example, for standard C(C(a,b),c), C(b,c) is standard. Also, in the combined system, the result is standard after a possibly repeated conversion C(Ω_{i+1},0) → Ω_{i}.

*Proof:* By recursion, it suffices to check when a=C(c,d), c is modified into c', and c' is standard. Since c' has no subterms between c' and c (or between C(c',d) and C(c,d), and similarly for certain subterms of c') and since the subterm tree is sufficiently preserved, the n-built from below criterion will carry over to c'.

**Variations using one-variable C:** If the system is expressed using C_{1} (one variable C), the maximality condition on *a* in C_{1}(a) may not be the simplest. A natural variation (for the n^{th} notation system) is to require *a* to be n-built from below from <C_{1}(a) (terms use 0, Ω_{n},'+', x→ω^{x}, and C_{1} for fix-points of x→ω^{x}) and another natural variation (though it is unclear whether it is too restrictive to get the strength) is to simply require for *a* to be n-built from below.

**Passthrough extension:** It is natural to try to extend the system by combining it with ideas from 8 Built-from-below with Passthrough. For example, let *a* be n+1-built from below from <b if the representation of *a* does not use ordinals above *a* except in the scope of an ordinal n-built from below from <b, where in representing C(c,d) for c<a, one only counts C(c,d) and ordinals ≤d and their subterms. This allows additional terms such as C(Ω_{2}+C(Ω_{2}*2+C(**C(Ω _{2}*3,0)**,C(Ω

a≺

a≺

where d(C(e,f))=e (for standard C(e,f)) and d(y)=∞ otherwise. The combined system can be defined as above. A natural restriction is to prevent entering n-built-from-below stage while we are in the passthrough. The passthrough might make the system much stronger (especially if delayed diagonalization is not a problem here), but given our lack of knowledge, also has a high risk of ill-foundedness. If full passthrough is a problem, a restricted version can still likely be used for iterating n-built-from-below, as described in 7 Iteration of n-built from below.

**Reflection configurations:** There is also a possible variation on the main system using 2.5 Reflection Configurations (see there for terminology); its strength and well-foundedness are unclear. The nth system will require that in C(a,b), r(a) is r(a),n-built-from-below, denoted by B_{r(a),n}(r(a)), or we are not using passthrough, 0,n-built-from-below. The combined system is as above.

B_{a,0}(d) ⇔ d < λx.x (i.e. reflection configuration d is a constant (below x))

B_{a,n+1}(d) ⇔ ∀x∈T_{d} (x⊏d ∧ r(x)>d) ∃y⊏d (r(x)⊆r(y) ∧ (r(y)<a ∨ B_{a,n}(r(y))).

*Notes:*

* An equivalent construction that avoids nested configurations is to require a≺_{r(a),n}C(a,b) (using standard comparison for C(a,b)), or ≺_{0,n} if not using passthrough, with

d≺_{a,0}b ⇔ d<b (note that d is an ordinal)

d≺_{a,n+1}b ⇔ ∀x∈T_{d} (x⊏d ∧ r(x)>r(d,b)) ∃y⊏d (r(x)⊆r(y) ∧ (r(y)<a ∨ y≺_{a,n}parent(y))).

* The scope of reflection configurations (which is narrower than the scope for ordinals) already gives us a form of passthrough, but the passthrough condition becomes relevant after our parsing leads into a higher configuration. For example, in the final stage, rather than being built-from-below (and thus in a sense, recursive), we have built-from-below with passthrough, which might be much broader.

* Given the triple permissiveness (n-built-from-below, reflection configurations, passthrough), this is the place for the interested reader to look for ill-foundedness, but quite possibly this is also the only version that actually reaches second order arithmetic with projective determinacy.

**Possibilities for the Strength**

Behind its simple definition, the main notation system hides subtle and unknown structure. Similar patterns repeat at different levels of the strength hierarchy, and here are five of the possibilities for its strength: (1) not well-founded, (2) rudimentary set theory + {there is α^{(+)n}-stable α: n∈ℕ} (3) second order arithmetic, (4) rudimentary set theory + {there is n-subtle cardinal: n∈ℕ}, (5) second order arithmetic with projective determinacy (perhaps using canonical projective ordinals).

Without a proof or a clear understanding of its structure, we cannot rule out (1). At the moment, (2) represents a lower bound on our intuitive ability to embed descriptions of ordinals into the notation system (and even there, I did not properly analyze structure at non-Gandy ordinals, which start appearing before α^{+}+1-stable); we do not expect the strength to be that low, but we do not yet see beyond that with a sufficient clarity. (3) corresponds to the similarity between the nth system and around n alternating quantifiers, and to a rough similarity between C_{i} in the passthrough system (8 Built-from-below with Passthrough below) and the usage of Ω_{i}. (4) often shows up in certain loosely similar problems (see Harvey Friedman's work and also (Taranovsky 2012)). Moreover, the relationship between the passthrough system and the main system at level of Π_{n}-reflection suggests a strength beyond (3). Going further, despite inclusion of small large cardinals, L has a Δ^{1}_{2} well-ordering (of ordinals countable in L). If second order quantifiers are fully used (corresponding to a Δ^{1}_{n} well-ordering), the strength would correspond to (5). A number of different natural additions to second arithmetic, including (conjecturally) comparability of Wadge degrees lead to projective determinacy. Our guess for the main system is (3), but we expect that a reasonable modification can be used to get (5). Perhaps, some combination of passthrough with n-built-from-below works (an example is given above). See 6.2 New Analysis for additional details (and possibilities).

Also, an intuitive analysis by user Hyp cos of a fragment of the main system (unmodified version) with a long list of examples can be found at http://googology.wikia.com/wiki/User_blog:Hyp_cos/TON,_stable_ordinals,_and_my_array_notation ; I have not verified its correctness.

**Differences from Degrees of Reflection C**

The n=2 notation system in 5 Main Ordinal Notation System is not identical to the one in 4 Degrees of Reflection. The notation system for degrees of recursive inaccessibility corresponds to the one in "Degrees of Reflection", and the assignments of ordinals in "Degrees of Recursive Inaccessiblity" and "Degrees of Reflection" should not be used for the main system. Let the standard C denote denote the notation system in "Main Ordinal Notation System".

C(C(Ω+C(Ω*2,0),C(Ω*2,0)),0) appears to be the "least" term valid for "Degrees of reflection" C but not for the standard C. However, this does not appear to adversely affect the strength of the standard C since enough ordinals remain available for the collapse. For example, in n=2 system, for every *a* built from below, for every b that uses only ordinals <a, C(C(a+b,0),0) is standard (after converting a+b to the standard form).

C(Ω_{2}+ε_{C(Ω2*2,0)+1},0) appears to be the "least" term valid for the standard C but not "Degrees of Reflection" C, and the difference appears to make the standard C for n=2 much stronger than C in "Degrees of reflection".

**Conjectured Hierarchy**

For standard C (with Ω=Ω_{2}), if d=C(Ω,C(Ω*2,0)), then C(Ω+d,0) should be the least recursively inaccessible ordinal. (Intuitively, since d is admissible but not limit of admissibles and for cofinally many representable e<d, C(1,e,0) is standard, C(1,d,0) should also be admissible.)

Continuing upward, C(Ω+d*2,0) should be the least recursively hyperinaccessible ordinal; C(Ω+d^{2},0) -- least recursively Mahlo, C(Ω+d^{d},0) -- least Π_{3} reflecting, and so on, analogously to the description from "Degrees of Reflection".

The hierarchy would suggest that C(Ω*2, 0) should be the least ordinal x such that L_{x} is a Σ_{1} elementary substructure of L, and this hierarchy is formalized below in 8 Built-from-below with Passthrough, which is a variation on a fragment of the main system. However, while the passthrough system makes certain collapses free, 2-built-from-below (without passthrough) gives one free collapse, which might be insufficient as we approach an ordinal *a* that is a^{++}-stable (or just Σ^{1}_{1}-reflecting). Roughly speaking, getting an ordinal d corresponding to a large level <a^{++} involves one collapse and arguments corresponding to <a^{+}, with a second collapse to get those arguments.

The level at which the main system reaches a^{++} stable ordinals is unclear. Essentially, the worst case scenario is that correctness n>1 corresponds to the closure of {α: α is α^{(+)n}-stable} (or even less, with Ω_{2} possibly being the least Σ^{1}_{1} reflecting ordinal). Consider c = C(Ω_{2}+a,b), and let f be an appropriate recursive ordinal function (using parameters <c; f(x)>x), and consider how f can be placed in *a*. In constructing c, the final collapse in the definition of f is free, which allows using f in many but not all places inside *a*. If we can show that the permitted places are enough, then α = C(Ω_{2}*2,0) would already correspond to α^{++}-iterations (or more if there is some stronger other structure). Note however, that places inside *a* that will be collapsed further impose a limit on the ordinals used in f (if placed there), which would not work for getting the strength.

While the definition of the main system is perhaps simpler than the passthrough system, the relationship between the ordinals and the notations appears more direct in the passthrough system, especially if the main system does not reach beyond second arithmetic. Assuming it is strong enough, the passthrough system probably works better for proving the exact ordinal strength of Z_{2}.

**Higher n:** If the strength of the main system corresponds to second order arithmetic, some conjectured assignments are as follows.

Ω_{n} (n>1) - as in the next section

C(C(C(Ω_{3}+1,0),0),0) - the proof ordinal of Π^{1}_{2}-CA_{0}, and analogously for Π^{1}_{n}-CA_{0}.

C(C(C(Ω_{3}+ε_{0},0),0),0) - the proof ordinal of Δ^{1}_{3}-CA, and analogously for Δ^{1}_{n}-CA.

C(C(C(Ω_{3}*2_{0},0),0),0) - the proof ordinal of Π^{1}_{2}+TR_{0}, and analogously for Π^{1}_{n}+TR_{0}.

**Levels of Correctness**

For terms in the notation system, assign correctness levels as in 4.4 A Step towards Second Order Arithmetic above. (See above for basic properties, but for example, Ω_{i} (i>0) is the least ordinal of correctness i.) If the notation system corresponds to Z_{2}, then we expect the following under the conjectured canonical assignment:

* 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_{ρ}.

**Note:** Here, ρ is an ordinal such that L_{ρ} satisfies ZFC minus power set. For definiteness, let ρ be ω_{1}^{L} since second order arithmetic does not prove existence ρ with L_{ρ} satisfying ZFC\P, but it proves as a schema that L_{ω1L} satisfies ZFC\P.

**Note:** Below is a set of (mostly wrong) guesses (retained for historical purposes) that were developed before a more modern understanding of the properties of the main system. The assignments assume that the main system corresponds to second order arithmetic.

**Ordinal Assignments**

After Π_{n} reflecting ordinals, the next set theoretical concept is that of stability. Here are ordinals corresponding to different levels of stability.

C(Ω_{2}^{+},0) -- the least ordinal *a* that is stable up to ε_{a++1} (note that Ω_{2}^{+} equals C(C(Ω_{3},Ω_{2}),Ω_{2}))

C(C(Ω_{3},Ω_{2}),0) -- the least ordinal stable up to 2 admissible ordinals

C(C(Ω_{3},Ω_{2})*Ω_{2},0) -- the least ordinal that is Π_{2} reflecting onto ordinals that are stable up to two admissible ordinals, and similarly with other levels of reflection

C(C(Ω_{3},C(Ω_{3},Ω_{2})),0) -- the least ordinal stable up to 3 admissible ordinals, and so on

C(C(Ω_{3}+Ω_{2},0),0) -- the least ordinal stable up to a recursively inaccessible ordinal

C(C(Ω_{3}+Ω_{2}^{2},0),0) -- the least ordinal stable up to a recursively Mahlo ordinal, and so on

C(C(Ω_{3}+C(Ω_{3},Ω_{2}),0),0) -- the least ordinal that is stable up to a larger ordinal that is stable up to two admissible ordinals

C(C(C(Ω_{3}*2,0),0),0) -- proof theoretical ordinal of Π^{1}_{2}-CA_{0}

C(C(Ω_{3}*2,0)+1,0) -- the least ordinal *a* such that L_{a} models KP + Σ_{1} separation (which has the same strength as Π^{1}_{2}-CA + TI), so its proof theoretical ordinal appears to be C(C(C(Ω_{3}*2,0)+1,0)^{+}, 0).

C(C(C(Ω_{3}*ε_{0},0),0),0) may be the proof theoretical ordinal of Δ^{1}_{3}-CA, which has the same strength as KP + {there is a Σ_{1} elementary chain of length *a*: *a*<ε_{0}}.

**Possible Alternative**

One issue with the notation system is that while C(Ω_{n+1}+1, 0) (n>0) is the height of the least Σ^{1}_{n}-correct model of Π^{1}_{n}-CA, the collapse C(C(Ω_{3}+1, 0), 0) corresponds to a weaker theory than Π^{1}_{2}-CA_{0}. The cause of this is our maximality condition for degrees which causes for example C(ε_{Ω2+1}, 0) to equal C(Ω_{2}^{+}, 0). If we could devise a corresponding notation system that distinguishes such terms, here are guesses for some of the proof theoretical ordinals:

For n>0, C(…C(Ω_{n+1}+1, 0)…, 0) (with n+1 Cs) -- the ordinal for Π^{1}_{n}-CA_{0}.

C(C(C(Ω_{3}, C(Ω_{3}+1, 0)), 0), 0) -- the ordinal for Π^{1}_{2}-CA + TI.

C(Ω_{3}*2, 0) -- the least ordinal κ of correctness 2 with L_{κ} satisfying KP + Δ_{2} separation.

C(C(C(Ω_{3}*2, 0), 0), 0) -- the ordinal for Π^{1}_{2}-TR_{0}.

C(C(C(Ω_{3}, C(Ω_{3}*2, 0)), 0), 0) -- the ordinal for Δ^{1}_{3}-CA + TI.

**Notes:**

* This subsection is retained for both intuitive and historical value. A more precise analysis of how C might reach ZFC and beyond is in the next section. Also, the three variable C described here corresponds with 8 Built-from-below with Passthrough system.

* Both the old (and especially) the new analysis assume some understanding of set theory. Useful references include (Jech 2006) and (Kanamori 2008).

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 (specifically, in L). 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 Ω^{2}+ω and L_{Ω*Ω}, and so on.

For a notation system, 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 arguably like in 3 Degrees of Recursive Inaccessibility (that is the standard form of b uses only ordinals below b), but the general case is unclear.

I do not have the conditions for *a* and *b* in the presence of uncountable cardinals. However, roughly speaking, the condition for *a* is being definable from below from <C(a,b,c). If a'<a, then C(a',b,c) is definable in L_{Ω+a} for every representable value of b provided that c < Ω and a' and c are definable in L_{Ω+a} (Ω+a (in both instances) is not sharp here, but it communicates the idea).

I also note that, for every finite n, to get an ordinal notation system for ZFC\P + "ω_{n} exists", it is sufficient to describe an ordinal notation system for ordinals between ω_{n} and ω_{n+1} where ordinals ≤ω_{n} are given as constants and ordinals ≥ω_{n+1} are represented in terms of ordinals <ω_{n+1} using a given notation system **O**. One can then stack the resulting systems on top of each other any finite (but fixed) number of times to get the full system for a particular n.

If the definition of C(a,b,c) is worked out, one can extend the system by adding a function that enumerates L-cardinals (or just cardinals). To get inaccessible cardinals, one can use constant 0 and a 4-variable C(a,b,c,d) where *a* indicates degree of inaccessibility. One guess is that going beyond 4-variables corresponds to higher order set theory, and that the strength for finite variable C corresponds to ZFC + {n-ineffable: n<ω} (plus a conservative higher order set theory extension to extend Ord to match the notation system). One can go further by adding ordinal Ω and using higher ordinals in place of n-tuples. To go still further, one would use Ω_{1}, Ω_{2}, ..., (analogously to the notation system for second order arithmetic) with the hope/ideal to capture second order arithmetic plus projective determinacy. However, we are still far from that.

**Collapsing functions**

One approach to find ordinal notation systems for ZFC and beyond is to find a set of functions that is rich enough to capture the set-existence principles but tame enough for comparison to be recursive. Let us start with 0, ordinal addition, ordinal exponentiation base ω, and add aleph function that enumerates infinite cardinals as computed in L. A key property of uncountable cardinals is unreachability from below; for example, every infinite model has a countable submodel. So to capture the unreachability, let us add function
f: f(a, b) → the least ordinal c such that c is not definable in L_{a} using parameters ≤b.

Two questions to ask are:

Is the resulting ordinal representation system recursive? (That is, is there an algorithm for comparing terms?)

If yes, how strong is the resulting system? Does it capture the full strength of the underlying set theory or does it correspond to recursive analogue (of cardinals) or something in between?

If f is not sufficient, one can try a full collapsing mapping and instead of just its critical point:

Coll(a, b) → the collapsing mapping for least elementary submodel of L_{a} that contains all ordinals ≤b (and in that case, include terms like Coll(a,b)(c) in the notation system)

To try to reach ZFC and beyond, we can add a 3-variable function

f: f(a, b, c) → the least a-inaccessible (in L) L-cardinal k > c that that is not definable in L_{b} using parameters <k

and ask whether the resulting representation system is still recursive, and if so, what is its strength.

To (try to) go to levels of indescribability, one can add function

g: g(a, b, c) → the least cardinal d > c such that for some cardinal e>d, there is elementary embedding j:Coll(e, d)(L_{e}) → L_{a} with crit(j) = d and j(d) = b.
To (try to) get to n-ineffable cardinals for all n<ω, one can use a predicate for n-reflective cardinals as computed in L (reflective cardinals are defined in (Taranovsky 2012)), and define g_{1}, g_{2}, ... that are like g except that Coll and j must also be elementary with respect to n-reflective cardinals (for n<i for g_{i}), but allowing Coll and j to "move" the predicates for reflective cardinals by application.

To go beyond that, one would use mice and the associated embeddings.

**An example notation system**

[*Update:* Retained for historical purposes, but 7 Iterations of n-built from below is (at present) a better candidate. Also, it is unclear whether the system is related to 8 Built-from-below with Passthrough, and the caveat of it being a guess (that possibly was not thought through) applies.]

To inspire future work, here is how a notation system (for ZFC+{n-ineffable}_{n<ω}) might look like, though it would be lucky if this particular system is well-founded and has the right strength. The system uses constant 0 and multivariable C. C(a_{1}, a_{2}, ..., a_{n}, b) corresponds to 2-variable C((a_{1}, ..., a_{n}), b) if (a_{1}, ..., a_{n}) is treated as an ordinal with lexicographical comparison, where after all leading 0s are removed, a longer sequence is larger than a shorter one, and (a_{1})=a_{1}, and standard form prohibits a_{1}=0. Thus (as written in 2.2 Basic Properties section for general C), it suffices to state the maximality condition.

(a_{1}, ..., a_{n}) is maximal in C(a_{1}, ..., a_{n}, b) iff for each i 1≤i≤n, a_{i} is <(a_{1}, ..., a_{n}) built from below from <C(a_{1}, ..., a_{n}, b).

*a* is <b built from below from <c if for every subterm e_{i} of *a* where e_{i} is is part of C(e_{1}, ..., e_{m}, f) (as an immediate subterm in the term tree of a) and e_{i}>a and on the path from *a* to e_{i} all ordinals are ≥c and ≤a, we have (e_{1},...,e_{m}) < b and e_{i} is <b built from below from <c.

The hierarchy is a bit different from the notation systems in previous sections. If d=C(1,0,C(2,0,0)), the least recursively inaccessible ordinal should be C(1,d,0), least admissible limit of recursively inaccessibles should be C(1,d*2,0), least recursively Mahlo C(1,d^{2},0), and so on.

Instead of n-tuples (as in (a_{1}, ..., a_{n})), we can use a stronger notation system — the construction can be formally generalized into a mapping that turns ordinal notation systems above generic ordinals (notation system above a generic ordinal is defined earlier in the paper) into stronger ones. As a particular example, we can use 2-variable C (in place of multivariable C), 0, and a large ordinal Ω, and treat ordinals ≥Ω as syntactic constructs. (Formally, given *a*, let variables range over subterms of *a*, including their position in *a*, and let '⊑' denote subterm (not necessarily a proper subterm, but different positions in *a* are distinguished), and '<' compare variables as ordinals. The maximality condition for *a* in C(a,b) is ∀s,t (s<t<Ω ∧ t⊑s ∧ ¬∃u⊒s s<u<Ω ∧ ¬∃u⊒t t<u<Ω ∧ ¬∃u⊒t u<C(a,b) ⇒ ∀v⊒t (¬∃w<Ω (t⊑w⊑v ∧ w≠t ∧ w≠v) ⇒ v<a)). Also, b<Ω⇒C(a,b)<Ω.)

*Introduction and notes:*

* This section provides insights about ordinals and cardinals (especially in L) and how a C-like system is likely to work there. The specific analysis is for a system behaving like 8.2 Degrees of Reflection with Passthrough but without delays in diagonalization. We refer to it as the n=2 system, though whether the main system for n=2 behaves like this is not clear. The system is (actually or hypothetically) extended to higher n analogously to the main notation system.

* If either the main system, or Degrees of Reflection with Passthrough, or a passthrough extension of the main system (or a system using reflection configurations) works like that, the analysis is (approximately) accurate for that system.

* The ordinal assignments may seem high, but keep in mind that in L, all reals are Δ^{1}_{2} in a countable ordinal, and if the notation system has mastered Σ_{α}-elementary substructures in L (and transitive collapses), the constructible versions of (small) large cardinals start to resemble the recursive versions (but with additional structure).

* If Degrees of Reflection with Passthrough (or a fragment considered, and especially if not using reflection configurations) is too weak, we conjecture that the assignment can still be defined and formalized by relying on the extensibility of the system (while keeping the assignment unchanged), though it is unclear how the extensibility should be formalized. Such an assignment would still qualitatively enhance our understanding of ordinals and cardinals, but there are points where it would fade out. One possibility is that for a theory T, models of T at definability level α are only captured if T is not too strong relative to (and has an appropriate definition at) the next definability level above α. Thus, the least rank-initial model of ZFC (or V_{δ}^{L}⊨ZFC) would likely be captured, but because ZFC is too strong relative to the concept of transitive models, the least transitive model of ZFC would not. Or more precisely (if the system is parameterized by an ordinal notation system **O** built above all ordinary ordinals), the supremum of the heights of the least transitive models of finite fragments of ZFC would then likely equal C(1,δ,0) where δ corresponds to the **O**-term (or diagonalization level) corresponding to the proof ordinal of ZFC.

**Note:** We will work in L (where V=L).

*Previous introduction:* To inspire future research, here is an optimistic guess about the strength of C. The assignments might be too low if I missed structure in the notation system or too high if I missed structure in L. I assume that the n=2 system is analogous to 8 Built-from-below with Passthrough (and in particular Degrees of Reflection with Passthrough) and in effect analyze that system, and that section (below) will help the reader to understand the discussion here. However, whether the analogy holds is unclear, and should the main system be too weak, the comments below for the n=2 system might still work for Degrees of Reflection with Passthrough (though it could be too weak as well), with n=3 and higher systems not yet defined (but see passthrough extensions to the main system for a possibility).

C(Ω*a+b,c) for b<C(Ω*a+b,c) should be ordinal number ω^{b} of definability/reflection level *a* above c (here Ω is Ω_{2}). Otherwise (b>C(Ω*a+b,c)), b has a canonical definition "b" (using ordinals <C(Ω*a+b,c) as constants), and C(Ω*a+b,c) is roughly the least ordinal corresponding to definability level *a* model of "b" (above c). For example, a=1 corresponds to transitive models, and (working in L and assuming we have enough strength and there is no acceleration or delay) C(Ω+ω_{ω}^{L},0) should be the least ordinal d such that for every finite n, there is a transitive model of ZFC\P+"ω_{n} exists" below d.

For simplicity (and insight), let us analyze the Σ_{2} hull of L. Here, we can have large cardinals but every set will be Σ_{2} definable, or Σ_{1} with the cardinality predicate. When *a* is sufficiently definable, c having definability/reflection level *a* corresponds to existence of structures <c of arbitrary complexity for (sufficiently definable) definability levels a'<a, allowing ordinals <c as parameters. For example, the least ordinal *κ* with L_{κ}≺_{Σ1}L is the least ordinal such that transitive models for arbitrary sufficiently satisfiable axioms exist below *κ*. Assuming the base theory gets its strength from the large cardinals it asserts, these axioms correspond to large ordinals/cardinals: structure for a transitive model → "b exists" → b (where large ordinal/cardinal *b* is canonically defined from below), and the models roughly correspond with C(Ω+b,0), so C(Ω*2,0)=κ.

Approximate definability level correspondence for c=C(Ω*a+a_{1},b):

small 1+a -- L_{c} is a Σ_{a} elementary substructure of L_{ω1} (c is countable, *a* may be transfinite, a=0 corresponds with L_{c} being admissible or limit of admissibles).

large a<Ω -- c is not Σ_{1} definable in (L_{κ+a}, ∈, Card) (Card is predicate for cardinals (in L)) allowing ordinals <c as constants, where κ is the least cardinal above c.

a=Ω -- cardinals. C(Ω^{2}+a,0) is ω_{ωa} for *a* below the least fix-point of the aleph function.

To go further, let us list some cardinals (in L) in the increasing order below the least inaccessible cardinal λ in L:

the least κ such that V_{κ} is a model of ZFC.

the least cardinal κ such that for some α, L_{α} satisfies "P holds and κ is inaccessible" where P is some large cardinal axiom that is compatible with L.

the least κ such that V_{κ} and V_{λ} satisfy the same Σ_{2} statements.

the least κ such that V_{κ}≺_{Σ2}V_{λ}. κ is also the least fix-point of f where f(a) is the least b such that V_{b} and V_{λ} satisfy the same Σ_{2} statements with parameters in V_{a}.

the least κ such that V_{κ}≺_{Σa}V_{λ}. For large 'a', one analog of this is the supremum of ordinals <λ that are Σ_{1}(Card) definable in L_{a} using parameters <κ.

Note the parallel between these notions and ordinals ≥λ that are below λ^{+} (the cardinal successor of λ), and our intuitive analysis suggests this analogy also applies to the notation system (hence the choice of the notation for the least inaccessible cardinal).

Let C(a,b,c,d) = C(Ω^{2}*a+Ω*b+c,d) and C(b,c,d) = C(0,b,c,d), and x^{+} = C(1,0,0,x) (the cardinal successor of x), and let S=C(1,1,0,0).

C(1,0,S,0) -- the least fix-point of x→ω_{x}.

C(1,0,C(1,0,S),0) -- a lower bound on the least power-admissible ordinal; we have not analyzed whether it is even higher.

C(1,0,C(2,0,S),0) -- might be the least cardinal κ such that V_{κ} and V_{λ} satisfy the same Σ_{2} statements, where λ is the least inaccessible cardinal.

C(1,0,C(2,0,S)*S,0) -- might be the least cardinal κ such that V_{κ}≺_{Σ2}V_{λ}, where λ is the least inaccessible cardinal.

C(C(ω,0,S),0) -- might be the proof theoretical ordinal of ZFC.

C(1,0,C(a,0,S),0) -- approximately the least cardinal κ that is not Σ_{1}(Card) definable in L_{a} (for appropriate large *a* ) using parameters <κ. Equivalently, it is the least κ that is inaccessible in the collapse of Σ_{1}(Card) Skolem hull of L_{a} where ordinals <κ are constants.

C(1,0,S^{+},0) -- the least inaccessible cardinal.

C(1,0,S^{+}+S,0) -- the least κ that is a limit of κ inaccessible cardinals.

C(1,0,S^{+}*2,0) -- the least hyperinaccessible cardinal.

C(1,0,S^{+}*C(2,0,S)*S,0) -- might be the least cardinal κ such that V_{κ}≺_{Σ2}V_{λ}, where λ is the least Mahlo cardinal.

C(1,0,S^{+}*C(a,0,S),0) -- approximately the least cardinal κ that is Mahlo in the collapse of Σ_{1}(Card) Skolem hull of L_{a} (for appropriate large *a*) where ordinals <κ are constants.

C(1,0,(S^{+})^{2},0) -- the least Mahlo cardinal.

C(1,0,(S^{+})^{3},0) -- the least hyper-Mahlo cardinal.

C(1,0,(S^{+})^{S+},0) -- the least greatly Mahlo cardinal.

C(1,0,S^{++},0) -- might be the least weakly compact cardinal κ (assuming representations for ordinals below κ^{++} can be sufficiently robust, as otherwise the least weakly compact could be lower).

C(1,0,S^{+(n+1)},0) -- might be the least Π^{n}_{1} indescribable cardinal.

C(1,0,a,0) -- approximately the least *a*-indescribable cardinal (for appropriate large ordinal *a*).

C(1,n,0,0) -- might be the least n-subtle cardinal.

Other possibilities for n-subtle cardinals are C(n+1,0,0,0) (with C(1,a,0,0) being approximately *a*-indescribable) or C(Ω^{n+1},0). While we do not see which set theoretical structures would raise the assignments this way, much uncertainty remains.

*More on cardinals after the first subtle cardinal:*

S is also the least cardinal κ such that for every S⊂κ, there is an S-indescribable cardinal <κ.

Let T = C(1,2,0,0).

C(1,1,C(1,0,a,T),0) -- (for appropriate large *a*) approximately the least *a*-indescribable limit of subtle cardinals.

C(1,1,C(1,1,0,T),0) -- the least subtle limit of subtle cardinals.

C(1,1,C(1,1,0,T)*T^{+},0) -- the least κ such that subtle cardinals are stationary below κ.

C(1,1,C(1,1,0,T)*C(1,0,a,T),0) -- (for appropriate large *a*) approximately the least *a*-indescribable subtle cardinal.

Beyond n-subtle cardinals, we have α-subtle cardinals where instead of an n-tuple of indiscernibles, we have a well-founded tree, with the indiscernity along each branch of the tree (but not necessarily between different branches). Formally, κ is α-subtle (α≤κ^{+}) iff for every α'<2+α, club C⊂κ, and regressive f:κ^{<ω}→κ, there is a well-founded tree of rank α' of ordinals in C such that every branch is an increasing tuple homogeneous for f. Note that a completely ineffable cardinal is α-subtle for every α, and is below the least 1-iterable cardinal. Possible assignment (low confidence):

C(1,α,0,0) -- approximately the least α-subtle cardinal (if α is not too large).

C(1,C(2,0,α,0),0,0) -- approximately the least α-iterable cardinal (in a generic extension where α is countable, and assuming the cardinal is above α).

C(1,P,0,0) -- (where P corresponds to a large cardinal axiom) approximately the least possible for a transitive model M of P, with every M-cardinal being a cardinal in L, with the M existing in a generic extension of L (note that M can have measurable cardinals and more).

Going further, recall that the above is in the Σ_{2} hull of L.

C(2,x,y,z) appears work similarly but with Σ_{3} hull of L, and so on.

C(α,0,0,0) -- the height of the transitive collapse of (approximately) Σ_{α} hull of L (assuming α<C(α,0,0,0)).

Beyond that, using n ordinals of degree Ω_{2}^{3}, we get hulls using about n Silver indiscernibles, allowing us to approach the true ω_{1}^{L}.

C(C(1,0,0,1,0),0,0,x) -- the least L-cardinal above x. At this point, we effectively have zero sharp, so successor infinite L-cardinals have effective cofinality ω (with the cofinality witnessed by the notation system).

C(C(1,0,0,1,0)*a,0,0,0) -- approximately the result of iterating the sharp operation *a* times.

Ω_{2} -- ω_{1}^{V}. We do not use ω_{1}^{HOD} because we expect that (analogously to ω_{1}^{L}) in an appropriate extension of the language of set theory, there is a canonical sequence of length ω converging to ω_{1}^{HOD}.

For the full n=2 system, ordinals <Ω may correspond to countable ordinals, and higher ordinals correspond to countable mice with mouse order <ε_{ω1+1} (or <ε_{Ord+1} among all mice). (A mouse is a generalization of L_{a} for canonical inner models.) C(a,b) roughly corresponds to ordinal height of the least mouse of order a' (a' depends on b), where a' is obtained from *a* by representing *a* in terms of ordinals <Ω and replacing each term a_{i} that is too large with a_{i}', where a_{i}' corresponds to a model of the description of a_{i} with the model having definability level corresponding to the position of a_{i} in *a*. For example, if C(Ω^{i}*a,0) corresponds to iterating some mouse operator M *a* times, then for large *a* it may correspond to the least model of "a" that is closed under M.

Beyond n=2, as of this writing, our understanding is very limited, so we present 3 options.

The low option assumes that we are missing something, and do not reach Woodin cardinals. For example, **Σ ^{1}_{n+3}** generic absoluteness is equiconsistent with n strong cardinals (with model also apparently having

For the main option, we note that in the nth system, we permit n drops, which corresponds to mice having, in some sense, complexity level n. Moreover, if ordinals correspond to real numbers, a drop corresponds to a quantifier, and mice capturing Σ_{n} truth correspond to about n-2 Woodin cardinals.

An old guess (just a guess) is that:

C(Ω_{3}*a,0) -- enough structure for (approximately) *a*-reflective cardinals, especially for a>ω (reflective cardinals are defined in (Taranovsky 2012)).

C(Ω_{3}^{a+1},0) -- measurable of order *a*.

For the (aspirational) high option, we transcend Woodin cardinals, with C(Ω_{3}+α,0) (or some other term) corresponding to a countable mouse with roughly α (or ω^{α}) Woodin cardinals. The most optimistic possibility is that ordinals of correctness n>2 correspond to (approximately) n-2-reflective cardinals (and their limits), and also that n-reflective cardinals agree with the critical sequence of an n-huge embedding. (Note that the first is about the level of expressiveness, while the second is about strength, and capturing n-reflective cardinals in V may or may not naturally correspond to reaching (approximately) n-huge cardinals analogously to how the expressivenss of second order arithmetic leads to the strength of Woodin cardinals.) The supremum of representable countable ordinals might then be ω_{1}^{HOD} (recall that reflective cardinals go beyond (V,∈) definability). Also, n-huge cardinals have a natural definition using a normal ultrafilter, and can also be characterized by M including a sufficient fragment of the embedding, j''(j^{(n)}(κ))∈M.

By iterating n-built from below, we get a candidate stronger notation system, but its strength and well-foundedness are unclear. The construction is similar to 8.2 Degrees of Reflection with Passthrough (especially for handling the limit stages of the iteration), but with additional complications. For relevant subterms we have to set the permissible n (for n-built-from-below) so as to prevent infinite regress, which we accomplish by reading off n from the portion of term that is sufficiently stable relative to the subterm.

**Notation System:**

**Syntax:** Two constants (0, Ω) and a binary function C.

**Comparison:** Standard. (For ordinals in the standard representation written in the postfix form, the comparison is done in the lexicographical order where 'C' < '0' < 'Ω': For example, C(C(0,0),0) < C(Ω, 0) because 000CC < 0ΩC.)

**Standard Form:**

0, Ω are standard

"C(a, b)" is standard iff

**1.** "a" and "b" are standard

**2.** b is 0 or Ω or "C(c, d)" with a≤c, and

**3.** Every a'<Ω in the representation of *a* in terms of ordinals <Ω representation of *a* is a''-n-built from below from <C(a,b). See below for definitions.

*Possible extension:* Use a-n-built from below (but n will still be based on a'').

**Definitions:**

**4.** *a* is a''-0 built from below from <b iff a<b.

*a* is a''-n+1 built from below from <b iff *a* does not use ordinals <Ω above *a* except

a. as a subterm of an ordinal a''-n built from below from <b or

b. as a proper subterm of C(c,d) with c<a'' that is not in the scope of a subterm of C(c,d) that is <C(c,d).

**5.** Testing for <C(a,b) can be done in the ordinary lexicographical order.

**6.** a'' is the part of *a* that is not affected by taking the limit a'→Ω, and n is maximal such that a'' (as a string in prefix form) has a (possibly empty) prefix 'C'*i + 'C0'*n, where '+' denotes concatenation and '*' denotes repetition (essentially, n is the integer part of the least significant part of a'').

**7.** To get the limit in (6), which will call a_{lim}, represent *a* in prefix form, delete everything to the left of a', replace a' with Ω, add the right number of Cs on the left to make the term well-formed (not necessarily standard), and then recursively replace C(d,C(e,f)) with C(d,f) where d>e (using standard comparison; replacement order does not matter). a'' (as a string) will be the largest common suffix of a and a_{lim}; if a'' is empty, replace it with 0.

**Extensions:** If for representing ordinals above Ω (in terms of ordinals <Ω), we use a given C (perhaps using Ω' to go beyond CNF), the above construction applies, with the limit in (6) obtained directly using nonstandard forms above Ω (it is unclear if the computation in (7) will work for typical C).

**Variation using CNF base Ω:**

(1)-(5) are as above, except as modified below.

**8.** In constructing the subterm tree of *a* (used below), ordinals ≥Ω are represented in Cantor Normal Form base Ω, which can be accomplished using the equation C(a,b)=b+ω^{a} iff *a* is ≤ the least fix-point of x→ω^{x} above b (the inequality always holds if b≥Ω). (Also, C(a,b)<Ω iff b <Ω.)

**9.** a'' is obtained by representing *a* in CNF base Ω and deleting all terms with significance level less than or equal that of a', where Ω^{c}*d is deleted if c or d is deleted, and '+' is deleted if d is deleted in c+d. The significance level of a term d<Ω in *a* (using CNF base Ω) is obtained by deleting everything to the right of d (but if d is inside e in Ω^{e}*f; f is replaced by 1), changing d to Ω and subtracting *a* on the left (and converting to standard form for comparison).

**10.** n=max(m∈ℕ: ∃d∈Ord c=d+m), where c is the rightmost ordinal <Ω in CNF base Ω representation of *a*, where c is to the left of a' and the significance level (as defined above) of c is higher than that of a' (and c is 0 if *a* has no terms of higher significance level than that of a').

**Notes:**

* In 4, the same ordinal may occur in several places in the subterm tree, and each occurrence is treated separately.

* In practice, one would use CNF base Ω for ordinals ≥Ω (also, one would likely prefer 1-variable C).

* A convenient variation is to use n+1 instead of n; it has the same strength but especially for a<Ω, more closely resembles our other systems.

* As written, if Ω^{c}*d is deleted because d is deleted, subterms of c might still be used for setting n.

* Nonstandard forms can be defined in the usual way: C(a,b) is the least ordinal >b that equals C(c,d) (standard form) for c≥a. (Or if we want to make C(a,b) total in b but partial in *a*, set C(a,C(b,c)) = C(a,c) if a>b, and after all these simplifications are complete, require the form to be standard.)

* A variation is to use a different ordinal notation system (instead of C) for ordinals ≥Ω. One can use an arbitrarily strong system as long as it has an appropriate structure for the combined system to work.

* A variation (apparently permitting fewer terms) is not to consider ordinals inside passthrough (4(b)) as candidates for a''-n built from below (4a), thus making the structure of C(c,d) above <C(c,d) irrelevant.

* *Reflection configurations:* Given our special use of the integer part, reflection configurations are only (unconditionally) defined above limit ordinals. For b+ω, configurations above <(b+ω) use a fictious limit ordinal x with b<x<b+ω. This limitation does not apply to configurations that do not use Ω (except in constants below x).

* The well-foundness of the possible extension is unclear. We still need to be strict about n so as to prevent infinite descending sequences like Ω, C(Ω+1,0), C(C(Ω+1,0)+2,0),... (each lower ordinal gets a higher permissible n).

To understand the system (using CNF base Ω), consider the segment that uses only C(a,b,c) = C(Ω*a+b,c) (with a,b,c <Ω). 4 requires that b is a-n-built from below from <C(a,b,c) where n is the integer part of a. (I use a-n in place of Ω*a-n; also in this segment *a* is automatically built from below from <C(a,b,c).) For a=n, this approximately corresponds with n built from below from c, which allows embedding of the main system (the one using Ω_{n}) into this segment with finite *a*. If the main notation system corresponds to Z_{2}+PD, for limit *a*, the level may correspond with J_{a}(ℝ), and then one repeats n-built from below construction but this time assuming that for lower levels definability has been completed, hence 4b. The sense of 4b is that C(c,d) is treated as representing C(c,d) in terms of ordinals <C(c,d), and which intermediate ordinals >C(c,d) are used is irrelevant.

The full system is a transfinite iteration of the above. Beyond Ω^{e} for a fixed small ordinal e, CNF base Ω becomes more complex, but using significance level should be the right generalization. In requiring a' to a''-n built from below (from <C(a,b,c)), we avoid circularity by requiring that, in a certain sense, a'' is constructed prior to a', which can be used to explain the construction of a''.

*Strength*: For all we know, if the main system corresponds to second order arithmetic or lower, the strength here might be only slightly higher than second order arithmetic (or even lower, or if above Z_{2}, just slightly below existence of L_{εω1+1}). However, if the main notation system (that uses Ω_{n}) reaches Z_{2}+PD, a reasonable hypothesis for the strength of this system below Ω^{Ω*ω} is rudimentary set theory + for every ordinal κ there are κ Woodin cardinals (with ordinals <Ω corresponding to Wadge ranks (within determinacy) that have a canonical definition in the theory). This appears to have the same strength as rudimentary set theory plus schema (n a natural number): Games on integers of countable length and projective payoff are determined, where the game consists of n rounds, with the first round having length ω and each round coding (with coding having projective complexity) the length of the next one. Ω^{a+1} may correspond with (approximately) ω*a Woodin cardinals, and Ω^{Ω+a} with (approximately) the number of Woodin cardinals equaling the value of (ω*a)th Woodin cardinal. The full system may correspond to games (of variable countable ordinal length) with a level n round (schema given n), where level m rounds consist of level m-1 subrounds, with the number of subrounds (or number of moves for level 1 rounds) determined at the start of each round. (This strength can also be expressed using limits of Woodin cardinals, and is well below a regular limit of Woodin cardinals.)

A question regarding this assignment of strengths is that if n-built-from-below leads to around n Woodin cardinals, what happens if the system were built using (say) 5-built-from-below throughout. On one hand, it is unclear what would prevent it from accumulating Woodin cardinals (at a slower rate, getting around kα (k<5) in place of ωα Woodin cardinals at similar points), but on the other hand, the construction appears weaker than (say) 7-built-from-below (in the main system). It is possible that our conjectured strengths are wrong, with a small chance that the main notation system already reaches n-huge cardinals.

**Further extensions:**

* While the strength can be increased slightly by going beyond ε_{Ω+1}, new construction principles are required to reach substantially further.

* One approach is to set n in some way that more closely approaches self-reference.

* Another approach is that in C(*a*,b,c), one would want to allow *a* to have a richer structure than b. Here is how it may look like, although the particular extension here is just an illustrative guess and might well be either ill-founded or failing to reach further. In 4 (above), for the variation using CNF base Ω, add clause

c. or the term f (a'<f<Ω) has lower significance level in e than that of a' in *a*, where e is the outermost (without intervening C) CNF base Ω superterm of f.

(Thus, it is more accurate to say (significance level of a' in a)-a''-n built from below. The significance level is for CNF base Ω and is as defined above. If f is e, the level is Ω. One can also consider the restriction below (for example) Ω^{ω}, where the significance level of a' in Ω^{n}a' is (essentially) n.)

**Reflection configuration version:** If iterations of n-built-from-below is weaker than expected, using 2.5 Reflection Configurations may allow the system to get the right strength. The definition combines the reflection configuration definitions for the main notation system and for Degrees of Reflection with Passthrough. Let r' denote r_{<Ω}. For comparing configurations, Ω stands for λx<Ω.Ω. The relevant condition will be that for every d<Ω in the representation of *a* in terms of ordinals <Ω, r'(d) is r'(a),n-built-from-below (or r'(a''),n for the unextended version), denoted by B_{r'(a),n}(r'(d)).

d is a,0-built-from-below iff it is a constant (below Ω = λx<Ω.Ω).

d is a,n+1-built-from-below iff (with quantifiers ranging over T_{d})

∀x⊏d (d < r'(x) < Ω) ∃y⊏d (r'(x)⊆r'(y)) (y<Ω ∧ B_{a,n}(r'(y)) ∨ parent(y)<Ω ∧ r'(y)<a).

**Future:** To get to n-huge cardinals, one would want to find how to place a corresponding embedding j in a simple framework.

Here we present a strong ordinal notation system with conjectured strength beyond second order arithmetic, and below (8.2 Degrees of Reflection with Passthrough) we hope to reach beyond ZFC. The system comes in two versions:

* The basic version whose well-foundedness we prove below (using large cardinals). It behaves very similar to the extended version (which makes it exceptionally precise in imitating second order arithmetic), except that because of delayed diagonalization, we suspect that it is weak.

* The extended version that uses reflection configurations and should have the right strength.

C_{i}(a,b) will be the least ordinal of reflection level i and for that level of degree *a* above b. The sense of reflection level i is that definitions for reflection levels <i have been completed in a sense that will be formalized by the notation system. The system can be described as built-from-below with passthrough for lower reflection levels.

*Relation with the main system:* C_{i}(a,b) superficially corresponds with the main system C(Ω_{2}*i+a,b) with a,b<Ω_{2} and *a* and b representable without using ordinals ≥Ω_{2}^{2}. However, the C_{i} system permits additional terms, including apparently all terms with C(Ω*i+a,b) valid for the Degrees of Reflection system, such as C_{0}(C_{1}(C_{2}(0,0),C_{2}(0,0)),0), and most likely, the main system misses too many terms for the above correspondence to approximately hold. In the other direction, not all valid main system terms that do not use ordinals ≥Ω_{2}^{2} become valid C_{i} terms; an example is (courtesy of Hyp cos) C(Ω_{2}+C(C(Ω_{2}*2+C(Ω_{2}+C(Ω_{2},C(Ω_{2}*2,0)),0),0),C(Ω_{2}*2,0)),0).

**Syntax:** Constant 0 (the least ordinal), and function C with 3 arguments.

**Standard form:**

C_{i}(a,b) is standard iff

- a and b are standard

- b is 0 or b is C_{j}(c,d) with (i,a)≤(j,c) (lexicographically). (This is needed for uniqueness of representations, but not needed for comparison.)

- a is built from below from <C_{i}(a,b) with passthrough for (C_{j}:j<i), that is *a* does not use ordinals above *a* except

-- as a subterm of an ordinal <C_{i}(a,b) (using standard comparison to check) or

-- as a proper subterm of C_{j}(e,f) where j<i that is not in the scope of a subterm of C_{j}(e,f) that is <C_{j}(e,f). In other words, C_{j}(e,f) is treated as representing the ordinal C_{j}(e,f) in terms of ordinals <C_{j}(e,f), and which intermediate ordinals >C_{j}(e,f) are used is irrelevant.

**Comparison:** Standard where (i,a) is treated as an ordinal ((i,a)<(j,b) ⇔ i<j ∨ i=j∧a<b). That is (assuming standard form)

C_{i}(a,b) ≤ d ⇒ C_{i}(a,b) < C_{j}(c,d)

b ≥ C_{i}(c,d) ⇒ C_{i}(a,b) > C_{j}(c,d)

otherwise, C_{i}(a,b) < C_{j}(c,d) iff (i,a) < (j,c).

**Example:** Let M=C_{2}(0,0), and for readability allow ordinal addition.

C_{1}(M+C_{1}(M*2,0),0) is invalid because M+C_{1}(M*2,0) uses a higher ordinal (M*2).

C_{1}(C_{0}(C_{3}(0,0),M),0) is valid because of the passthrough for C_{0}. As far as C_{1} is concerned, we are not using C_{3}(0,0) as an ordinal but merely as a notational shorthand to define C_{0}(C_{3}(0,0),M) in terms of M.

On the other hand, in the first example, M+C_{1}(M*2,0) = C_{0}(C_{1}(M*2,0),M) and C_{1} "knows" what is C_{0}(C_{1}(M*2,0),M) in terms of C_{1}(M*2,0) and M but cannot handle C_{1}(M*2,0) because M*2 is larger than M+C_{1}(M*2,0).

**Proposition:** In the definition of C_{i}(a,b), it is sufficient to allow ordinals ≤b as constants. For the passthrough it does not matter whether we use ≤f or <C_{j}(e,f).

**Note:** Out of the four equivalent possibilities here, we chose the one that makes sense for reflection configurations.

**Proof:** Regarding passthrough, all terms strictly between f and C_{j}(e,f) have degree <(j,e), so passthrough applies to those terms as well. Regarding ≤b vs <C_{i}(a,b), assume contrary, and let b'>b be minimal such that *a* is built from below (with the passthrough) from ≤b' (because b' is a subterm of *a*, minimality does not require proving well-foundedness). b' is C_{j}(a',b'') with j<i or j=i ∧ a'<a, and in both cases *a* is built from below (with the passthrough) from <b', contradicting minimality.

**Building the system above an ordinal:** The system can also be built above any given ordinal α. One version is to add ordinals <α as constants and to have C_{i}(a,b)≥α. Another version with the same strength is to add ordinals ≤α and (for standard forms) only use C_{i}(a,b) for b≥α; its benefit is that C_{i} need not depend on α.

Terms that are built-from-below typically correspond with recursive terms, or to ordinals below the proof ordinal of the theory represented. Since built-from-below terms are captured by C_{0}, a natural assignment is to set C_{1}(0,x) as the next admissible ordinal above x. Moreover such assignment is canonical in its ability to keep existing terms unchanged as one extends C_{0} to a stronger recursive system. The relationship for higher C_{i} and C_{i+1} is analogous. We conjecture that this extensibility (properly formulated) can be used to formally define the canonical assignment of ordinals (and that the strength of the system corresponds to (or is weaker than) the assignment).

**Reflection Configuration Version**: If (as it seems likely; see proof ordinals below), the delay in the ability to do diagonalization affects the strength, our remedy is to use 2.5 Reflection Configurations rather than degrees. In (for example) C_{j}(c,M) (j≥i) as part of C_{i}(a,b), the relevant test will be not whether c<a, but whether what c is to C_{j}(c,M) is less than what *a* is to C_{i}(a,b), which is expressed using reflection configurations.

**Formalization:** In the subterm tree (with terms in different positions distinguished) for C(a,b), let r(c) for c in C_{j}(c,d) be the reflection configuration of c above C_{j}(c,d); these are the only configurations we consider. In the definition of the system, replace "*a* does not use ordinals above *a*" with "*a* does not use reflection configurations >r(*a*)".

**Notes:**

* Out of j,e,f, only e can be bigger than C_{j}(e,f). Thus, in the original version, it suffices to test e (for being >a), and in this form, the only difference (from using reflection configurations) is in how e is tested.

* All terms valid in the basic version are also valid here because in the relevant case, C_{i}(a,b) < C_{j}(e,f).

**One variable C:** We will use 2.4 One Variable C, with C'_{i}(ω^{an}+...+ω^{a1}) = C_{i}(a_{1},...,C_{1}(a_{n},0)..)) (standard term). Note that C'_{i}(0) = 0 and C'_{i}(ω^{2}) = C_{i}(ω2,0).

**Conjectured Strength:** A natural conjecture is that the C_{n} system (n>0, terms only use C_{i} for i≤n) corresponds to Π^{1}_{n}-TR_{0}. (TR stands for transfinite recursion and 0 indicates limited induction.) For the conjectured natural assignment of gaps, C_{1+i} returns ordinals κ such that L_{κ}≺_{Σi}ω_{1}^{L} for i>0, allowing transfinite i, and C_{1} returns admissible ordinals and their limits, and with ordinals below C_{1}(0,0) recursive. The proof theoretical ordinal of second order arithmetic is likely C_{0}(C_{ω}(0,0),0) = C'_{0}(C'_{ω}(1)). The full system may then correspond to (canonical countable ordinals in) rudimentary set theory plus for every countable α, L_{ω1+α} exists. This has the same strength (and the same canonical countable ordinals) as second order arithmetic with comprehension for infinitary formulas, axiomatized using the truth predicate or satisfaction relation for such formulas.

**Examples (conjectured canonical assignment):**

Let M = C_{2}(0,0) = C'_{2}(1), and let x^{+}=C_{1}(0,x), and N = M^{+}.

C'_{1}(a) for a<M enumerates admissible ordinals <M and their limits, C'_{1}(M+a) enumerates fix-points of the above enumeration, C'_{1}(M*a+b) corresponds to 2-variable enumeration of the fixpoints, and so on for ordinals recursive in M (that is for ordinals <M^{+}). C'_{1}(N+a) (a<N=M^{+}) enumerates recursively inaccessible ordinals <M and their limits, and so on with N being similar to Ω in 4 Degrees of Reflection. For example, C'_{1}(N^{NN2+N}*16+N^{NN}*15+N^{N}*N*14+N^{N}*13+N^{2}*12+N*11+10) should be the 10th admissible above the 11th recursively inaccessible above the 12th recursively hyperinaccessible above the 13th recursively Mahlo above the 14th admissible limit of recursively Mahlo ordinals above the 15th Π_{3} reflecting ordinal above the 16th Π_{3} reflecting ordinal that is Π_{2} reflecting onto Π_{4}-reflecting ordinals. Note that while diagonalization in "Degrees of Reflection" uses built-from-below ordinals <Ω, here we first collapse a built-from-below ordinal into an ordinal <M^{+} (or another appropriate ordinal), and then use it (using passthrough).

Going further, for appropriate f, C'_{1}(f(M)) is roughly the least ordinal c that is f(c) stable. However, this is approximate.

* For example, C'_{1}(M^{++}) is the least Σ^{1}_{1}-reflecting c (and thus the least non-Gandy c) as opposed to the least c^{++} stable c. Also, for non-Gandy κ, C_{1}(0,κ) appears to be the supremum of κ-recursive well-orderings of κ, with the next admissible above κ being C_{1}(0,(C_{1}(0,κ)) instead, or even higher for very strong reflection levels (or if we missed essential structure). (Also, since M is non-Gandy, N is not an admissible ordinal.)

* C'_{1}(φ_{M++}(1)) (using Veblen φ) could be the least ordinal that is both Π^{1}_{1} and Σ^{1}_{1} reflecting.

* C'_{1}(φ_{M+n}(1)) (n>2) could be the least ordinal stable up to n-1 admissibles.

* C'_{1}(M^{+ω}) = C'_{1}(C_{1}(1,M)) is likely the least ordinal that for every n<ω is above an ordinal that is stable up to n admissibles.

* C'_{1}(φ_{M+} (M^{+ω}+1)) is likely the least ordinal that for every n is Π^{1}_{1}-reflecting onto κ^{+n}-stable κ . The use of φ appears analogous to the assignment of degrees for "Degrees of Reflection" above; different reflection levels can be combined and iterated similar to that assignment.

* C'_{1}(M^{+(ω+1)}) is likely the least κ^{+ω}-stable κ.

* For the basic version, the least ordinal stable up to a recursively inaccessible ordinal is likely C'_{1}(C'_{2}(2)^{+}). This is the because C'_{2}(2)^{+} = C_{2}(0,M)^{+} is required to get the first recursively inaccessible ordinal above M, I = C_{1}(C'_{2}(2)^{+},M) (and I is the first relevant ordinal that requires C'_{2}(2)^{+}). The least ordinal Π^{1}_{1}-reflecting onto ordinals stable up to a recursively inaccessible is likely C_{1}(C'_{2}(2)^{+}+φ_{M+}(I+1),0), and similarly with other ordinals. However, for the reflection configuration version, built-from-below is more permissive, and the ordinals are C'_{1}(I) and C'_{1}(φ_{M+}(I+1)), respectively.

* For the basic version, the least ordinal above x<M stable up to a nonprojectible ordinal could be C_{1}(C'_{2}(ω)^{+},x), in which case the height of the least transitive model of Π^{1}_{2}-CA is C_{1}(C'_{2}(ω)^{+}+1,0). For the reflection configuration version, use C'_{2}(2) in place of C'_{2}(ω).

**Additional Intuition:** In c = C_{i}(a,b) (for the standard choice of *a*), let M = C_{i+1}(0,b). c is the least ordinal >b that satisfies (approximately) T, where T denotes the reflection properties of M up to *a* (using ordinals <c in C_{i}(a,b) as constants), and (as a description) T works at absoluteness level i. Now, C_{i}(a,b) is monotonic (including in *a*), and to achieve that, the standard *a* is built-from-below using functions that are sufficiently absolute between c and M. For example, C_{0}(a,b) gives a recursive-in-b ordinal, and the ability to use passthrough for C_{0} corresponds to Π^{1}_{1}-absoluteness for appropriate transitive models. Now, Σ_{i} elementary substructures agree about Σ_{i} formulas, and each increase in i corresponds to an extra quantifier, or an extra definability level for the passthrough.

**Proof ordinals in the reflection configuration version:** The use of reflection configurations can replicate the structure ω times. For example, the system with all subterms below C'_{1}(2) corresponds to KP, but ε_{0} = C'_{0}(C'_{1}(1)) < C'_{0}(C_{0}(C'_{1}(2),C'_{1}(1))) < C'_{0}(C_{0}(C_{0}(C'_{1}(3),C'_{1}(2)),C'_{1}(1))) < ... < C'_{0}(C'_{1}(2)) = the proof ordinal for Π^{1}_{1}-CA_{0}, with each term in the above sequence essentially adding an extra admissible to KP. It appears that the replication happens at each admissible, leading to C'_{0}(C'_{1}(ω)) being the proof ordinal for Π^{1}_{1}-CA_{0} + ω^{ω} admissibles.

C'_{0}(N) is likely the proof ordinal for Π^{1}_{1}-CA_{0} + ω recursively inaccessible ordinals, and similarly with N^{2} and recursively Mahlo ordinals, and so on.

C'_{0}(C'_{i}(2)) is likely the proof ordinal for Π^{1}_{i}-CA_{0}.

C'_{0}(C'_{i+1}(1)) is likely the proof ordinal for Π^{1}_{i}-TR_{0}.

**Layering and delayed proof ordinals:**

However, for the basic version, C'_{0}(C'_{2}(n)) for n≤ω is only the proof ordinal of Π^{1}_{1}-TR_{0} + n recursively inaccessible ordinals. To see this, let T_{i,c} (for sufficiently definable c) be the notation system where (1) no term or subterm is ≥c, (2) the *i*th recursively inaccessible ordinal is assigned to C'_{2}(i), and (3) in place of terms <C'_{2}(i), all ordinals <C'_{2}(i) are used as constants. If T_{i+1,c} is well-founded, then so is T_{i,c} because recursiveness of T_{i+1,c} combined with the recursive inaccessibility allows us to carry out an ordinal assignment. Formulated in a different and more specific way, instead of setting C_{1}(0,x) as the next admissible ordinal, we can set it to the proof ordinal (built above x) of Π^{1}_{1}-TR_{0} + (n-i) recursively inaccessible ordinals, where C'_{2}(i)≤x<C'_{2}(i+1). Similar layering for C'_{i}(n) also happens with higher i.

We have not ruled out that (for appropriate a<C'_{2}(ω)) C_{0}(C'_{2}(ω)+a,x) "unlocks" the strength of *a* above x, but our expectation is low. C_{0}(C'_{2}(ω) + C'_{1}(n),0) (n>1) appears to be the proof ordinal of KP + there is a limit of recursively inaccessible ordinals and n-2 admissibles above it. A lower bound on C_{0}(C_{2}(ω)*α,0) is the proof ordinal for Π^{1}_{1}-CA_{0} + ωα recursively inaccessible ordinals, using diagonalization to express α > C'_{2}(ω). This lower bound (and its generalization to other limits) is insufficient to rule out correspondence with 3 Degrees of Recursive Inaccessibility (with C_{0}(C_{i+1}(ω)) being the proof ordinal of Π^{1}_{1}-CA_{0} + ω recursively i-inaccessible ordinals), or between 4 Degrees of Reflection and 8.2 Degrees of Reflection with Passthrough.

Ordinal notation systems can be characterized by (1) the kind of diagonalization they permit, and (2) by how high up you have to go to carry out diagonalization. On the first point, we have enough structure for second order arithmetic. However, on the second point, the notation system (without reflection configurations) resembles 3 Degrees of Recursive Inaccessibility. To give an example, while getting a diagonalization of admissibles (in typical systems) can be done above the next recursively inaccessible ordinal, here we have to wait until C_{2}(0,0). Note that even if C_{0} is too weak in the full system, the canonicity of the above (partially given) assignment remains (besides correspondence with the reflection configuration version) in the ability to keep the assignment unchanged as one extends C_{0}, including in 8.2 Degrees of Reflection with Passthrough.

The built-from-below with passthrough for lower levels system can be extended by adding more variables. One extension (not the one below) which might be too restrictive is as follows. With C_{a,b}(c,d), c may use passthrough for C_{a',b'} where (a',b')<(a,b) (lexicographically) and b may use passthrough for C_{a',b'} where a'<a. To go further, combine a, b, and c into an ordinal using a large ordinal Ω and naturally (using CNF base Ω) extend the combination up to ε_{Ω+1}. The result will be the "Iteration of n-built from below" notation system with "n-built from below" replaced with "built from below". However, the above is probably too restrictive, and in C_{a,b}(c,d) we should allow passthrough for b where (a',b')<(a,b). A natural extension up to ε_{Ω+1} (or another ordinal) is the following.

**Degrees of Reflection with Passthrough:**

*Syntax:* 0 (the least ordinal), C (partial binary function), Ω (a large ordinal), **O** (ordinal notation system for ordinals above Ω in terms of ordinals <Ω).

*Choice of O:* CNF base Ω; another choice is C; any system that is well-founded above a generic ordinal should work.

*Description:* C is as in General Notation. C(a,b)<Ω when b<Ω. In C(a,b), each d in the representation of *a* in terms of ordinals <Ω is built from below from <C(a,b) allowing passthrough for C(a',b') where a'<a. This means that d does not use ordinals x with d < x < Ω except in the scope of an ordinal <C(a,b) or as permitted by passthrough. Passthrough means that C(a',b') is treated as representing C(a',b') in terms of ordinals ≤b', and the intermediate ordinals used are not checked for being <d.

**Notes:**

* Like in the C_{i}(a,b) system, in built-from-below from <C(a,b), we can replace "<C(a,b)" with "≤b". Similarly, for the passthrough, it does not matter whether we use ≤b' or <C(a',b').

* The passthrough is the only difference from 4 Degrees of Reflection. The only difference in Comparison Algorithm is that the condition using T_{a} is now:

∀x∈T_{a} ∀y⊏x (x<y<Ω) ∃z⊒y (z<Ω) (z⊐x ∨ z < C(a, b) ∨ z⊐y ∧ d(z)<a ∧ ∀t (y⊑t⊑z) t≥z)

where d(C(e,f))=e (for standard C(e,f)) and d(z)=∞ otherwise. "z⊐y ∧ d(z)<a ∧ ∀t (y⊑t⊑z) t≥z" is the passthrough condition. I did not verify conversion of nonstandard forms.

* Omitting z⊐y (thus permitting z=y in passthrough) would make the system ill-founded. An example infinite descending sequence is (courtesy of Hyp cos) a_{1} = M = C(Ω*2,0) and a_{n+1} = C(Ω+M*a_{n},0).

* While it permits many additional terms, we have not ruled out that (for typical **O**), it has the same strength as Degrees of Reflection. If that is the case, see the reflection configuration version below for a much stronger system (whose well-foundedness is unclear).

If the system is well-founded (which is not yet proved), a natural conjecture is that it is similar to and has the same strength as the main system for n=2, or a hypothetical passthrough variation of the main system for n=2. See 6 Beyond Second Arithmetic (above) for analysis.

An example is C(a,b,c,d) with (a,b,c) compared lexicographically. Note that allowing passthrough for b using (a,b') (b'<b) allows b to use large values of c' even when using *a*. While seemingly unrestricted, this only appears to be useful in the presence of large enough gaps that there is no sign of infinite regress. The passthrough for c using (a,b,c') (c'<c) is only relevant when b>c (note that a < C(a,b,c,d) here) given the built-from-below condition.

**Proposition:** The C_{i}(a,b) system above permits the same terms that are <Ω (and with the same comparison) as degrees of reflection with passthrough using pairing for O and identifying C_{i}(a,b) with C(Ω*i+a,b).

**Proof:** The only difference not addressed above is passthrough for (i',a') with i'=i and a'<a, but this is vacuous. Assume contrary, and consider a shortest length counterexample C(Ω*i+a,b) with a prohibited subterm c' = C_{i}(a',b') < a. Because c' is valid in the C_{i}(a,b) system and c'<a, the inability to use passthrough for c' does not invalidate the term, contradicting the assumption.

*Note:* The proposition relies on i < max(a,C(Ω*i+a,b)) and does not fully apply to extensions. A counterexample is C(Ω*i+C(Ω*i,j),0) with i = C(Ω^{2}*2,0) and j = C(Ω^{2},0).

*Restricted passthrough:* To formalize a framework for restrictions, in addition to **O**, one specifies a restriction p on passthrough: Given *a* and a subterm (including position) d<Ω in the O representation of *a*, return p(a,d). The condition using ∀x∈T_{a} would use d(z)<p(a,x) in place of d(z)<a. For example, the multivariable built-from-below with passthrough for lower levels would use p(Ω^{i}*a_{i}+...+Ω*a_{1}+a_{0}, (j,a_{j})) = Ω^{i}*a_{i}+...+Ω^{j+1}*a_{j+1} (this is 0 if i=j; in p(..), j is used to indicate the position of a_{j}). If the unrestricted system (i.e. p(a,..)=a) were ill-founded (or just inconveniently strong), then between a safe choice (used above and in Iteration of n-built-from-below) and the ill-foundedness, there would be a spectrum of possibilities, with degrees of reflection with passthrough acting as a framework rather than a single system.

*Equivalent definition of Degrees of Reflection with Passthrough:*

* The subterm tree for a term d < Ω in terms of ordinals <c with passthrough for <a (and treating ordinals ≥Ω as syntactic constructs) is as follows.

d is the root node.

Given d' in the tree:

d'<c (or d'=0) -- d' is the leaf node.

Otherwise, d' = C(a',b') (standard form), and

- if a'<a, the immediate subterms are the terms <d' (equivalently, leaf terms <Ω) in the standard representation of d' in terms of ordinals <d'. This is the passthrough condition.

- else the immediate subterms are b' and the terms <Ω in the standard representation of *a'* in terms of ordinals <Ω (note that the representation is trivial if a'<Ω).

* C(a,b) is standard if the standard conditions are met (a and b are standard, and b is 0 or Ω (if using C above Ω) or C(c,d) with a≤c) and for every d<Ω in the representation of *a* in terms of ordinals <Ω, for every term f in the subterm tree for d in terms of ordinals <C(a,b) with passthrough for <a, f≤d.

*Note:* Restricted passthrough is defined analogously, using "... with passthrough for <p(a,d) ...". (Also, the use of <C(a,b) allows even a very restricted passthrough such as p(a,..)=0.)

**Reflection Configuration Version:** Using 2.5 Reflection Configurations, the reflection configuration version of the system is obtained by replacing the condition using T_{a} with:

∀x∈T_{a} ∀y⊏x (r_{<Ω}(x) < r_{<Ω}(y) ∧ y<Ω) ∃z⊒y (z<Ω) (z⊐x ∨ z < C(a, b) ∨ z⊐y ∧ r_{<Ω}(d(z)) < r_{<Ω}(a) ∧ ∀t (y⊑t⊑z) t≥z)

(the only change is the use of r_{<Ω}).

* Equivalently, the above definition using the passthrough subterm tree is modified as follows.

- Replace a'<a with r(a',d') < r(a,C(a,b)); the subterm tree is otherwise unchanged.

- Replace f≤d with r(f,par(f)) ≤ r(d,C(a,b)), where par(f) is the parent of f in the above passthrough subterm tree; the parent of d is C(a,b).

*Note:* Subterms in different positions are distinguished. Use standard comparison for C(a,b) (as if nonstandard C does not exist).

We first present a proof in ZFC of well-foundedness of C_{0},C_{1},C_{2} system, and then (using a different approach) a proof of well-foundedness of the full C_{i} system using a measurable cardinal. Then, we will build on that proof to prove well-foundedness of an extension. The proofs are for the version that does not use reflection configurations.

**C _{0}, C_{1}, C_{2} system**

**Theorem:** C_{0},C_{1},C_{2} system is well-founded, even if built above an arbitrary ordinal.

**Proof:**

Work in the constructible universe L.

Set C_{2}(a,b)=ω_{b'+ωa} where b' is the maximal ordinal such that ω_{b'}≤b (and b'=0 if b<ω_{1}).

(Note: Instead of C_{2}, we could have used a function f to enumerate uncountable cardinals (in L). For the notation system, if 'a' is standard, then so is 'f(a)'; f(a)<f(b)⇔a<b, f(a)<C_{0}(c,d)⇔f(a)≤d, f(a)<C_{1}(c,d)⇔f(a)≤d.)

Let C_{1}(a,b) be the least c>b that is not Σ_{1}(Card) definable in L_{κ+a}, allowing ordinals <c as constants, where κ is the least uncountable cardinal >b and Card is the predicate for cardinals (in L).

C_{0}(a,b), when defined, is the least c>b such that a'<a ∧ b'<c ∧ (C_{0}(a',b') is defined) ⇒ C_{0}(a',b')<c.

C_{0}(a,b) is defined iff *a* can be represented using C_{0}, C_{1}, C_{2} and ordinals <C_{0}(a,b) as constants such that

- all intermediate ordinals are below a.

- each use of C_{0} and C_{1} is standard in the following sense:

-- if C_{0}(c,d) is used as a subterm, then c does not use ordinals ≥c except in the scope of an ordinal <C_{0}(c,d)

-- if C_{1}(c,d) is used as a subterm, then c does not use ordinals ≥c except in the scope of an ordinal <C_{1}(c,d), or as a subterm of C_{0}(e,f) that is not in the scope of a subterm g≤f of C_{0}(e,f).

*Proposition:* If *a* is below the least fix-point of x→ω^{x}, then C_{0}(a,b)=b+ω^{a}.

*Proof:* Simple, by recursion on a.

*Proposition:* For every a, there is b' such that C_{0}(a,b) is defined iff b≥b'.

*Proof:* Choose the least b' such that *a* is representable (in the required sense) using ordinals <C_{0}(a,b').

*Proposition:* C_{0}(a,b) is monotonic in b, and for the class of *a* such that C_{0}(a,b) is defined, strictly monotonic and continuous in a. When defined, C_{0}(a,b) is the least point in the range of x→C_{0}(a,x) above b.

*Proof:* By construction of C_{0}.

*Proposition:* Standard comparison for C_{0}: C_{0}(a,b) < C_{0}(c,d) iff C_{0}(a,b) ≤ d or (b < C_{0}(c,d) and a<c) (assuming both are defined).

*Proof:* Follows from the above properties.

*Proposition:* In the definition of C_{0}, one could replace <C_{0}(a,b) with ≤b.

*Proof:* By recursion on a. An ordinal c with b<c<C_{0}(a,b) equals C_{0}(a_{1},C_{0}(a_{2},...C_{0}(a_{n},b)...)) with each a_{i}<a.

*Proposition:* C_{1}(a,b) is monotonic in *a* and b, and continuous in *a*.

*Proof:* By construction of C_{1}; monotonicity is the reason we used Σ_{1} definability. Continuity holds because for each *a* the class of ordinals that are not sufficiently definable is closed except at cardinals.

*Definition:* *a* is maximal in C_{1}(a,b) iff C_{1}(a+1,b)>C_{1}(a,b).

*Proposition:* *a* is maximal in C_{1}(a,b) iff *a* is Σ_{1} definable in L_{κ+a+1}, allowing ordinals <C(a,b) and cardinals as constants.

*Proof:* Given a Σ_{1}-definition of *a*, the definition of C_{1}(a,b) becomes Σ_{1} in L_{κ+a+1}, hence *a* is maximal. Conversely, if *a* is maximal, then C_{1}(a,b) is by definition Σ_{1} definable in L_{κ+a+1}, and this definition can be converted into a Σ_{1}-definition of a.

These properties lead to the standard comparison for the notation system provided that we can show two things:

* C_{1}(0,b)>C_{0}(a,b)

* *a* is maximal in C_{1}(a,b) when C_{1}(a,b) is standard.

Suppose that we can show that C_{0}(c,d) is recursive (or just Σ_{1}) in field(c:d) where field(c:d) consists of d and ordinals ≤d obtained by parsing term c into ordinals ≤d. Then the above conditions are met since C_{1}(a,b) is above all recursive-in-b ordinals, and *a* has a Σ_{1} definition obtained by parsing its notation and using the values of C_{0}(c,d).

*Proposition:* Standard comparison works in the system.

*Proof:* Suppose that standard comparison works below a, that is for every base ordinal b<a, when all subterms are <a, the comparison works. Allow terms using a. C_{0}(c,d) equals d plus the order type of the system between d and C_{0}(c,d). The built-from-below condition ensures that all ordinals <C_{0}(c,d) are representable in terms of ordinals ≤ d while using only ordinals <a, thus the comparison is standard and hence the system is recursive in field(c:d) as required.

**End of Proof**

**C _{i} system**

**Theorem:** Assuming an inner model with a measurable cardinal, the C_{i} ordinal notation system is well-founded, even if built above an arbitrary ordinal.

**Proof:**

Let K be the core model below a measurable cardinal, and let I_{α} be the predicate for ω(α+1)-reflective cardinals for K. See (Taranovsky 2012) (including section Iterations of Reflectiveness) for background, but the properties we will use are the following:

* Elements (and finite increasing n-tuples of elements) of I_{α} are good indiscernibles in (K, ∈, α, (I_{β})_{β<α}): φ(x)⇔φ(y) provided that x and y are finite subsets of I_{α} of the same cardinality, where φ is expressible in the model, and allowing sets in V_{min(x∪y)}^{K} as parameters. Access to the restricted I is allowed as a two variable function (so one can quantify over β in I_{β}).

* α<β⇒I_{β}⊂I_{α}

* K satisfies separation and replacement for predicates that use I.

Let F_{α} consist of functions that are definable in (K, ∈, (I_{β})_{β<α}) (allowing ordinals ≤α as parameters, I is treated as a two variable function), with each element of F_{α} taking a tuple of ordinals as input and returning an ordinal at least as large as the supremum of tuple.

When defined, C_{i}(a,b) is the least ordinal c in I_{i} such that C_{i}(a',b')<c if a'<a and b'<c and C_{i}(a',b') is defined, and

C_{i}(a,b) is defined iff *a* is built from below from <C_{i}(a,b) in the ith extension of the notation system. That is *a* must be representable as a term in that system such that all subterms are ≤a but allowing ordinals <C_{i}(a,b) as constants. In representing *a*, the ith extension uses functions in F_{i} and C with j≥i in C_{j}(b,c) where b does not use ordinals >b except in a term inside C_{l}(g,h) (l<j) that is not in a subterm of C_{l}(g,h) that is ≤h, where a subterm includes its position in the term.

(By recursion on a, this definition is noncontradictory and complete, except that we have not proved that ith extension is a really an extension.)

*Proposition:*

1. C_{i}(a,b) is the least ordinal in the range of x→C_{i}(a,x) above b.

2. C_{i}(a,b) is strictly monotonic in *a* (when it is defined).

3. For every i and a, there is minimum b' such that C_{i}(a,b) is defined iff b≥b'

4. If i<j and b < C_{j}(c,d), then C_{i}(a,b) < C_{j}(c,d)

5. C_{i}(a,b) < C_{j}(c,d) iff C_{i}(a,b) ≤ d ∨ b≤C_{j}(c,d) ∧ (i,a)<(j,c)

*Proof:* 1-3 standard. For 4, the condition C_{i}(a',b')<c corresponds to a closed unbounded set of possible c, and elements of I_{i} are stationary below every element of I_{j}. Statement 5 follows from the above properties and the definition.

Thus, the C_{i} ordinal notation system is well-founded provided that we can show that standard terms are valid in the constructed system. The only problem is that C_{i}(a,b) may use C_{j}(c,d)<a where j<i and c uses ordinals >a in a restricted way. The solution is to compute C_{j}(c,d) without computing term c as an ordinal.

Let d'' be the maximal (as an ordinal or under standard comparison) subterm of C_{j}(c,d) that is <C_{j}(c,d); d'' is expressible using ordinals ≤d and C_{j'} for j'≤j. Replace each C_{k}(e,f)>d'' with C_{k}(e,d'') where f<d'', and represent C(c,d) in terms of subterms ≤d'', so the representation will be a code in the standard form for the notation above d'', plus a list of ordinals ≤d''. We want to show that for some function in F_{i}, its application to the code and the list ordinals equals C_{j}(c,d) (which will complete the proof).

Recursive test for whether e = C_{j}(c,d):

* ∀e'<e C_{j}(c,d) ≠ e', and

* For every c'<c and d≤d'<e, C_{j}(c',d')<e where c' uses jth extension of the system.

By recursion, this solves the problem provided that we can test whether c'<c and C_{j}(c',d') is valid, and we can be overstrict with validity provided that at least one representation passes the test.

Overstrict validity test of C_{j}(c',d') (ordinals ≤d' are constants):

For every subterm C_{k}(e,f):

- f≥d'

- if f<C_{j}(c',d'), then f=d'

- e≤c'

- e does not use ordinals above e except in a term inside C_{l}(g,h) (l<k) that is not in a subterm of C_{l}(g,h) that is ≤h, where a subterm includes its position in the term.

Comparison when doing the validity test:

- two C terms - standard

- C term and an ordinal (ordinals ≤d' and their values after functions in F_{j}) -- C term is greater

- otherwise, represent both terms in terms of C terms (do not parse the C terms yet) and ordinals. Pairwise compare all the C-terms. Assign the C-terms to arbitrary ordinals in I_{j} >d' consistent with the comparison. Compute both ordinals and compare. This is the point where we use the indiscernibility of I_{j}.

To compare c' with c (assuming C_{j}(c',d') and C_{j}(c,d) were tested valid and d≤d'<C(c,d)):

- Use the comparison above. Even though d' need not equal d, the comparison of C terms with ordinals works since c does not have C-terms >d that are ≤d' (if it did, we would have replaced d with d'' above).

The procedure could fail in three ways:

- We got comparison as ordinals of terms valid for C_{j} system wrong -- not possible given the analysis above.

- We failed to include a valid ordinal -- not possible since (apart from a strictness in representations), we fully covered the definition of C_{j}.

- We included an invalid ordinal.

Suppose that the computation fails (is wrong) for C_{i}. Then there is invalid C_{i}(a,b) in the ith extension which we treated as valid. Let C_{j}(c,d) be an invalid subterm of C_{i}(a,b) with j,c,d valid. Then j>i, and c has a subterm C_{k}(e,f) (i≤k<j) for which our computation fails. This means that there is invalid C_{k}(e',f') that we treated as valid with e'≤e<a (and f'≥f). Iterating, we get an infinite descending sequence of ordinals (since e and, for each iteration, its analogue are valid), which completes the proof.

*Note:* If we can rule out overflows (where C_{i}(a,b)≥C_{i+1}(0,b)), the measurability assumption can be weakened to "starting at zero, the sharp operation can be iterated any ordinal number of times".

**Reducing the assumption:** Σ_{i} elementary substructures of L_{ω1L} lack indiscernibility but it may be possible to restrict F_{i} to a class of functions that guarantee the invariance of comparison. To check validity and compare C_{i}(a,b) with C_{i}(a',b) (a and a' are given as codes, with each C_{j(c,d)} having d≥b and with ordinals ≤b used as constants), it is sufficient to know the codes and the relative ordering of the ordinals ≤b that we used, and it may be possible to restrict F_{i} to an analogous class of functions (though perhaps with special conditions on b or other ordinals). One would also need sufficient definability of C_{i} to prove C_{i}(a,b)<C_{i+1}(0,b). Intuitively, validity of C_{i}(a,b) implies that *a* has a canonical definition of a certain type, which we can then 'drop' in an order preserving way to get a similar structure at a lower level.

**A fragment of Degrees of Reflection with Passthrough**

We only have a proof of well-foundedness of (a variation on) a small fragment of the system.

**Theorem:** Assume that there is an inner model 1+α measurable cardinals, where α is an ordinal. The C_{i}(a,b) system is well-founded even if augmented with α constants with (1) there is no constant c (c>0) with b<c≤C_{i}(a,b) and (2) in C_{i}(a,b), i is built from below from <C_{i}(a,b) with passthrough for lower values of i.

**Corollary:** Suppose that for every κ<min(δ: L_{δ}≺_{Σ1}L) there is a transitive model of "ZFC + κ measurable cardinals". Then for every α, the C_{i}(a,b) system with α constants is well-founded.

**Proof of the Corollary:** This follows from Σ^{1}_{2} correctness of L_{δ}.

**Notes:**

* This theorem/proof is only for the basic (rather than reflection configuration) version, so (despite the impression below) the system could be weak (possibly at the level of many recursively Mahlo ordinals).

* One possibility is that under conjectured canonical assignment, each constant corresponds to an uncountable cardinal in L. The notes below assume that to be the case. However, as of this writing, we cannot rule out a lower assignment, including one where each constant simply corresponds to an ordinal not Σ_{1}(ω_{1}^{L}) definable in L_{(ω1L*2)} from lower ordinals. However, the latter seems too low (unless we fail to reach Z_{2}) as (using ω_{1}^{L} for the first constant >0), C(ω_{1}^{L},b,c) (with c<ω_{1}^{L}) appears to correspond to κ with L_{κ}≺_{Σκ}ω_{1}^{L} (and thus not Σ_{1}(ω_{1}^{L}) definable in L_{(ω1L+κ)}), and thus appear sufficient to capture ordinals Σ_{1}(ω_{1}^{L}) definable in L_{(ω1L*2)}.

* Because of layering between different constants, for finite α, the strength is only expected to be around existence of α ordinals that are uncountable up to an admissible ordinal. I do not know if a similar collapse of strength also happens for infinite α.

* Unlike in the countable case, the least ordinal c such that L_{c} and L_{ω2L} satisfy the same Σ_{1}(Card) statements is below the least Σ_{1}(Card) elementary substructure of L_{ω2L}, and we have not determined the exact canonical assignment.

* The theorem and the proof suggest that in the table of cardinals and their recursive analogs, regular uncountable cardinals in L are recursive analogs of measurable cardinals.

* By iterating the construction (α → order type of the system) ω times (starting at 0), the ordinal we get (C(C(Ω^{2}+C(Ω,0),0),0)) is probably the proof theoretical ordinal for rudimentary set theory plus ∀α<ω_{1}^{CK} ∃s=ω_{α}^{L}. This is stronger than Zermelo set theory but weaker than Borel determinacy. Iterating it another time (for a total of ω+1 times) is equivalent to using a function to enumerate all C_{1}(0,0) constants and should give us all canonical ordinals in the theory.

**Proof of the Theorem:**

The proof is analogous to the proof of well-foundedness of ordinary C_{i}(a,b), but there are key differences which we will now cover in detail. Work in M, where M is the minimal inner model with 1+α measurable cardinals. The constants will be measurable cardinals and their limits, excluding the supremum of the measurable cardinals. Let κ_{m} be the second cardinal above the supremum of measurable cardinals. The exact fine structure is unimportant, but we can for example set M_{a} to L_{a}[U] where U codes the sequence of ultrafilters.

*Definition:* I_{i} (below the supremum of measurable cardinals) is defined as follows: λ∈I_{i} iff λ and κ satisfy the same Σ_{1}({j(M_{κm})}) predicates in j(M_{κm+i+1}) with parameters in M_{λ}, where κ is the least measurable cardinal (in M) above λ and j is the corresponding embedding.

We will use only the following properties of I_{i}.

*Definition:* getmin(i) is the least ordinal such that i is Σ_{1}({M_{κm}},getmin(i)) definable in M_{κm+i+1}.

*Proposition:*

* For all measurable κ, I_{i} has measure 1 below κ.

* I_{i} is uniformly-in-i Σ_{1}({M_{κm}},i) definable in M_{κm+i+2}.

* i<j ⇒ I_{j}\(getmin(i)+1) ⊂ I_{i}

* For all finite subsets s and t of I_{i} with ∀(measurable κ) |s∩κ|=|t∩κ| and Σ_{1}({M_{κm}}) φ with two free variables, ∀x∈M_{min(s∪t)} M_{κm+i+1} ⊨ (φ(x,s)⇔φ(x,t)).

*Proof:*

The indiscernity holds because for every λ∈I_{i} below measurable κ (κ is the least measurable above λ) for every finite increasing iterate M' of M with the first embedding using κ, (κ,s) agrees with (λ,s) for the relevant class of formulas where s is the set of critical points >κ used in the embeddings. Here, increasing means that the critical points are increasing. The agreement holds because the embeddings are sufficiently definable in M_{κm+i+1}.

*Notes:*

* Elements of I_{i} are effectively indiscernibles except as to the number of measurable cardinals below the element.

* Our setup ensures that above getmin(i) elements of I_{j} are indiscernibles even for predicates that use I_{i} for i<j.

The ith extension is defined analogously to the proof of the previous theorem. Both i and *a* need to be built from below from <C_{i}(a,b). Instead of j,a,b→C_{j}(a,b) for j<i, we will allow x→y=F(n,x) when:

x is a tuple of ordinals.

y is Σ_{1}({M_{κm}},x) definable in M_{κm+i+1}; n is a code for the definition.

y is an ordinal >max(x).

there is no measurable κ with max(x)<κ≤y.

An equivalent condition on i is that getmin(i)<C_{i}(a,b). This is easily seen equivalent to i being built from from below from <C_{i}(a,b), allowing F as above.

As before, to show that standard terms are valid in the system we constructed, we propose computation of C_{i}(a,b) where *a* is given as a term (in the ith extension) rather than ordinal. The comparison of terms is essentially as before. Since getmin(i)<C_{i}(a,b), comparison with i works. The comparison between a C or F term and one of the measurable constants is trivial. When assigning C-terms to indiscernibles, each indiscernible must have the right number of measurable cardinals below it.

Suppose that the computation fails (is wrong) for C_{i}. Then there is invalid C_{i}(a,b) in the ith extension which (in our computation) we treated as valid. Let C_{j}(c,d) be an invalid subterm of C_{i}(a,b) with j,c,d valid. Then, j or c has a subterm C_{k}(e,f) (i≤k<j) for which our computation fails. (Otherwise, C_{k}(e,f) would be sufficiently definable. Also, if k≥j, the use of C_{k}(e,f) would not prevent C_{j}(c,d) from being valid even if our computation of C_{k}(e,f) fails.) This means that there is invalid C_{k}(e',f') that we treated as valid with e'≤e<a (and f'≥f). Iterating, we get an infinite descending sequence of ordinals (since e and, for each iteration, its analogue are valid), which completes the proof.

Here is a technique that may permit getting well-foundedness of C in the weakest system possible, though as of this writing, we do not have a proof of correctness, and it is unclear whether the definitions give us the desired C. The key idea is that instead of defining C using complex ordinal recursion, we define C directly using canonical definitions of its arguments, with the twist that the arguments are interpreted not just in V but in other appropriate models. The systems can be built above an arbitrary ordinal, but otherwise, only standard terms are valid. The assignments below leave more gaps than is canonical; the canonical assignment remains unclear.

*Typical General Construction:*

Ordinals ≥Ω are treated as syntactic constructs.

A valid term C(a,b)<Ω is evaluated as the least ordinal κ>b such that there is a structure M, and an ordinal (or well-ordering) a':

* M is based on κ (each notion makes this specific) and satisfies a correctness/closure condition based on a'.

* a' is the result of

- taking the definition of *a* and (outside of M) replacing terms ≤b with ordinals. C(c,d) for d<b is replaced with its value, or if C(c,d)>b, with C(c,b) (below, the later is done implicitly).

- applying the resulting definition inside M. (If the application fails, this M is ruled out.)

By induction on the complexity of terms, the definition (once specified) is complete. Note that applying the definition inside M may lead to a computation in M'∈M (with appropriate terms precomputed in M), and so on.

We start with the three-variable C, using C(i,a,b) in place of C_{i}(a,b). We can optionally require that C(0,a,b) = b+ω^{a} when 'a' is below the least fix-point x→ω^{x} above b, but this appears unnecessary to get the right strength. We allow the system to be built above an arbitrary ordinal (within bounds), and similarly for the four variable and other extensions.

Here is one choice of assignment. For a valid term, C(a,b,c) will be the lowest ordinal κ>max(a,c) such that L_{κ} is a Σ_{1+a} elementary substructure of L_{ω1L} and some level of L satisfies "κ is ω_{1} and κ+a+b exists" where "b" is the canonical definition of b above c. The canonical definition is the one using C and ordinals ≤c as constants (see Typical General Construction above).

A more optimal choice that uses minimal assumptions for the fragment corresponding to Z_{2} is the following: C(a,b,c) is the least a*κ+b'-stable κ>max(a,c) with L_{κ} a Σ_{a} elementary substructure of L_{ω1L} where b' is b computed inside L_{κ} but with subterms ≤c replaced by constants (outside of L_{κ}). A further step to optimality is to use Σ_{a-1} elementarity for finite *a*, using admissible ordinals for a=1, and using no gaps (if all ordinals ≤c are permitted) for C(0,b,c). To complete the optimality, one would apply a construction similar to 4.3 Assignment of Degrees, but it is unclear how to extend it to the high strength level here.

*Degrees of reflection with passthrough:* While the system is likely stronger than this (unless it is below Z_{2}), if it were defined more narrowly so as to correspond to L_{εω1L+1}, the following construction might work: C(a,b) is the least κ with L_{κ+a'} elementarily embeddable into some L_{ω1L+a''} with critical point κ, where a' is obtained from *a* by representing *a* in terms of ordinals <Ω, replacing terms ≤b with constants, and then interpreting the resulting expression in L_{κ} (instead of L_{ω1L}). Also, the assignment of individual ordinals can be optimized by separating *a* as a_{1}*Ω+b_{1}, using Σ_{a1} elementary substructures (using diagonalization to get a_{1}≥ω_{1}), and using appropriate levels of stability for b_{1}. It is unclear whether this interpretation satisfies C(Ω*C(Ω^{2},0)+C(Ω^{3},0),0) < C(Ω*C(Ω^{2}+1,0),0) (a typical example in Degrees of Reflection with Passthrough). If it does and there are no other issues, that would suggest that the strength of Degrees of Reflection with Passthrough is only rudimentary set theory + ∀α "L_{ω1α} exists".

**Four Variable C**

For the four variable extension C(a,b,c,d) (based on degrees of reflection with passthrough), the following might work. Even if the above construction works, the ideas here might be applicable to other systems. Roughly, *a* corresponds to the level of indiscernibles preserved, b to the correctness for that level, and c to the object being modeled. Let Ω be a sufficiently-closed ordinal, and let I_{a} be indiscernibles of level a<Ω for V_{Ω}; for each *a*, Ω is the maximum element of I_{a}. ∀b>a I_{b}⊂I_{a}. Furthermore, I_{a} are good indiscernibles for V_{Ω} augmented with (as a single symbol) (I_{a'}:a'<a). Here, 'good' means that the indiscernibility holds even if allow parameters whose rank (as a set) is below the least indiscernible in a tuple. Regarding Ω, require that for every a<Ω such that V_{Ω+a} exists (this qualification is relevant for weak theories), Ω is a-I-indescribable: For every U⊂V_{Ω}, there is Ω'<Ω such that (V_{Ω+a},∈,I,U) and (V_{Ω'+a},∈,I,U) satisfy the same statements with parameters in V_{Ω'}. Since ∀b<Ω Ω∈I_{b}, I-indescribability (for a>0) ensures that ∀b<Ω' Ω'∈I_{b}.

For a valid term, C(a,b,c,d) will be the least Ω'>d such that

- V_{Ω'+b'} and V_{Ω+b'} satisfy the same statements with parameters in V_{Ω'}, allowing (I_{a'}:a'≤a) as a (single) predicate symbol. Here b' is the least ordinal such that for some I' agreeing with I_{a'} for a'≤a, (Ω,I') satisfies the definition of (Ω,I) in V_{Ω+b'+1}, with b' obtained by taking the C-definition of b above d (that is using ordinals ≤d as constants), and replacing I with I'.

- For some I' agreeing with I_{a'} for a'≤a, (Ω',I') satisfies the definition of (Ω,I) in V_{Ω'+b'+c'+1}. Here, c' is given by the C-definition of c above d, using (Ω',I') in place of (Ω,I).

Thus, Ω' is in I_{a}. Also, (it appears that) b' is below the next element of I_{a+1}. The built-from-below requirement should ensure that comparison works correctly provided that we preserved enough structure for the passthrough ability. Here, that structure is the level of indiscernibility, and for the final level reached, the level of agreement with Ω. Beyond that, built-from-below should let us get away with simulated structures: I' for b and (a different) (Ω',I') for c.

Starting with the minimum inner model L[U] with a measurable cardinal, the required indiscernibles can be constructed (using U and indiscernible in the model obtained by iterating U away) in a standard way. Also, it appears that we only care about indiscernibility of 1-tuples (with ordinal parameters). Furthermore, there is likely a weakening by using indiscernibles from a's iteration of the sharp that gets the exact strength of the notation system (perhaps for an extension of the system with additional terms). In that weakening, simulated indiscernibles (such as I') can be constructed in L (and other weak models) using a generic extension that makes Ω countable; L[(I_{a'}:a'≤a)] is used in place of V. To get optimality, Ω (or the starting Ω) can be chosen as the least element of I_{a+1} above d; the extent of I' will depend on b and (for Ω') c. Assuming it works and is optimal, the strength is that of "rudimentary set theory plus the sharp operation can be iterated any ordinal number of times".

REFERENCES

Arai, Toshiyasu (2015), "A simplified ordinal analysis of first-order reflection", arXiv:1506.05280.

Duchhardt, Christoph (2008), "Thinning Operators and Π_{4}-Reflection", thesis, http://d-nb.info/98.3428.3/34.

Jech, Thomas (2006). *Set Theory* (3rd edition). Springer.

Kanamori, Akihiro (2008). *The Higher Infinite: Large Cardinals in Set Theory from Their Beginnings* (2nd edition). Springer.

Rathjen, Michael (1994), "Proof theory of reflection", Annals of Pure and Applied Logic 68, pp. 181–224.

Rathjen, Michael (2006), "The art of ordinal analysis", International Congress of Mathematicians, II, Zürich, Eur. Math. Soc., pp. 45–69.

Rathjen, Michael (2014), "Omega-models and well-ordering principles", Foundational Adventures: Essays in Honor of Harvey M. Friedman (Neil Tennant (ed.)). (College Publications, London, 2014) 179-212.

Stegert, Jan-Carl (2010), "Ordinal proof theory of Kripke-Platek set theory augmented by strong reflection principles", thesis, https://nbn-resolving.org/urn:nbn:de:hbz:6-44449504436.

Taranovsky, Dmytro (2012), "Reflective Cardinals", arXiv:1203.2270.