Ordinal collapsing function

In mathematical logic and set theory, an ordinal collapsing function is a technique for defining certain recursive large countable ordinals, whose principle is to give names to certain ordinals much larger than the one being defined, perhaps even large cardinals, and then "collapse" them down to a system of notations for the sought-after ordinal. For this reason, ordinal collapsing functions are described as an impredicative manner of naming ordinals.
The details of the definition of ordinal collapsing functions vary, and get more complicated as greater ordinals are being defined, but the typical idea is that whenever the notation system "runs out of fuel" and cannot name a certain ordinal, a much larger ordinal is brought "from above" to give a name to that critical point. An example of how this works will be detailed [|below], for an ordinal collapsing function defining the Bachmann–Howard ordinal.
The use and definition of ordinal collapsing functions is inextricably intertwined with the theory of ordinal analysis, since the large countable ordinals defined and denoted by a given collapse are used to describe the ordinal-theoretic strength of certain formal systems, typically subsystems of second-order arithmetic, extensions of Kripke–Platek set theory, Bishop-style systems of constructive mathematics or Martin-Löf-style systems of intuitionistic type theory.
Ordinal collapsing functions are typically denoted using some variation of either the Greek letter or .

An example leading up to the Bachmann–Howard ordinal

The choice of the ordinal collapsing function given as example below imitates greatly the system introduced by Buchholz but is limited to collapsing one cardinal for clarity of exposition. More on the relation between this example and Buchholz's system will be said below.

Definition

Let stand for the first uncountable ordinal, or, in fact, any ordinal that is an -number and guaranteed to be greater than all the countable ordinals that will be constructed.
We define a function , taking an arbitrary ordinal to a countable ordinal, recursively on, as follows:
In a more concise way:
Here is an attempt to explain the motivation for the definition of in intuitive terms: since the usual operations of addition, multiplication and exponentiation are not sufficient to designate ordinals very far, we attempt to systematically create new names for ordinals by taking the first one that does not have a name yet, and whenever we run out of names, rather than invent them in an ad hoc fashion or using diagonal schemes, we seek them in the ordinals far beyond the ones we are constructing ; so we give names to uncountable ordinals and, since in the end the list of names is necessarily countable, will "collapse" them to countable ordinals.

Computation of values of ''ψ''

To clarify how the function is able to produce notations for certain ordinals, we now compute its first values.

Predicative start

First consider. It contains ordinals and so on. It also contains such ordinals as. The first ordinal that it does not contain is [Epsilon numbers (mathematics)|]. The upper bound of the ordinals it contains is , but that is not so important. This shows that.
Similarly, contains the ordinals which can be formed from,,, and this time also, using addition, multiplication and exponentiation. This contains all the ordinals up to but not the latter, so. In this manner, we prove that inductively on : the proof works, however, only as long as. We therefore have:
Now but is no larger, since cannot be constructed using finite applications of and thus never belongs to a set for, and the function remains "stuck" at for some time:

First impredicative values

Again,. However, when we come to computing, something has changed: since was added to all the, we are permitted to take the value in the process. So contains all ordinals which can be built from,,,, the function up to and this time also itself, using addition, multiplication and exponentiation. The smallest ordinal not in is .
We say that the definition and the next values of the function such as are impredicative because they use ordinals greater than the ones that are being defined.

Values of ''ψ'' up to the Feferman–Schütte ordinal

The fact that equals remains true for all.. However, at , the construction stops again, because cannot be constructed from smaller ordinals and by finitely applying the function. So we have.
The same reasoning shows that for all, where enumerates the fixed points of and is the first fixed point of. We then have.
Again, we can see that for some time: this remains true until the first fixed point of, which is the Feferman–Schütte ordinal. Thus, is the Feferman–Schütte ordinal.

Beyond the Feferman–Schütte ordinal

We have for all where is the next fixed point of. So, if enumerates the fixed points in question we have, until the first fixed point of the itself, which will be . In this manner:

is the Ackermann ordinal,
is the "small" Veblen ordinal,
is the "large" Veblen ordinal,
the limit of,,, etc., is the Bachmann–Howard ordinal: after this our function is constant, and we can go no further with the definition we have given.

Ordinal notations up to the Bachmann–Howard ordinal

We now explain more systematically how the function defines notations for ordinals up to the Bachmann–Howard ordinal.

A note about base representations

Recall that if is an ordinal that is a power of , any ordinal can be uniquely expressed in the form, where is a natural number, are non-zero ordinals less than, and are ordinal numbers. This "base representation" is an obvious generalization of the Cantor normal form. Of course, it may quite well be that the expression is uninteresting, i.e.,, but in any other case the must all be less than ; it may also be the case that the expression is trivial.
If is an ordinal less than, then its base representation has coefficients and exponents : hence one can rewrite these exponents in base and repeat the operation until the process terminates. We call the resulting expression the iterated base representation of and the various coefficients involved the pieces of the representation, or, for short, the -pieces of.

Some properties of ''ψ''

The function is non-decreasing and continuous.
If with then necessarily. Indeed, no ordinal with can belong to ; so is closed by everything under which is the closure, so they are equal.
Any value taken by is an -number. Indeed, if it were not, then by writing it in Cantor normal form, it could be expressed using sums, products and exponentiation from elements less than it, hence in, so it would be in, a contradiction.
Lemma: Assume is an -number and an ordinal such that for all : then the -pieces of any element of are less than. Indeed, let be the set of ordinals all of whose -pieces are less than. Then is closed under addition, multiplication and exponentiation. And also contains every for by assumption, and it contains,,,. So, which was to be shown.
Under the hypothesis of the previous lemma, .
Any -number less than some element in the range of is itself in the range of . Indeed: if is an -number not greater than the range of, let be the least upper bound of the such that : then by the [|above] we have, but would contradict the fact that is the least upper bound — so.
Whenever, the set consists exactly of those ordinals all of whose -pieces are less than. Indeed, we know that all ordinals less than, hence all ordinals whose -pieces are less than, are in. Conversely, if we assume for all , the lemma gives the desired property. On the other hand, if for some, then we have already remarked and we can replace by the least possible with.

The ordinal notation

Using the facts above, we can define a ordinal notation for every less than the Bachmann–Howard ordinal. We do this by induction on.
If is less than, we use the iterated Cantor normal form of. Otherwise, there exists a largest -number less or equal to : if then by induction we have defined a notation for and the base representation of gives one for, so we are finished.
It remains to deal with the case where is an -number: we have argued that, in this case, we can write for some ordinal : let be the greatest possible such ordinal. We use the iterated base representation of : it remains to show that every piece of this representation is less than . If this is not the case then, by the properties we have shown, does not contain ; but then , so, contradicting the maximality of.
Note: Actually, we have defined canonical notations not just for ordinals below the Bachmann–Howard ordinal but also for certain uncountable ordinals, namely those whose -pieces are less than the Bachmann–Howard ordinal. This canonical notation is used for arguments of the function.

Examples

For ordinals less than, the canonical ordinal notation defined coincides with the iterated Cantor normal form.
For ordinals less than, the notation coincides with iterated base notation : e.g., will be written, or, more accurately,. For ordinals less than, we similarly write in iterated base and then write the pieces in iterated base : so is written, or, more accurately,. Thus, up to, we always use the largest possible -number base which gives a non-trivial representation.
Beyond this, we may need to express ordinals beyond : this is always done in iterated -base, and the pieces themselves need to be expressed using the largest possible -number base which gives a non-trivial representation.
Note that while is equal to the Bachmann–Howard ordinal, this is not a "canonical notation" in the sense we have defined.

Conditions for canonicalness

The notations thus defined have the property that whenever they nest functions, the arguments of the "inner" function are always less than those of the "outer" one. For example, does not occur as a notation: it is a well-defined expression, but it is not a notation produced by the inductive algorithm we have outlined.
Canonicalness can be checked recursively: an expression is canonical if and only if it is either the iterated Cantor normal form of an ordinal less than, or an iterated base representation all of whose pieces are canonical, for some where is itself written in iterated base representation all of whose pieces are canonical and less than. The order is checked by lexicographic verification at all levels.
For example, is a canonical notation for an ordinal which is less than the Feferman–Schütte ordinal: it can be written using the Veblen functions as.
Concerning the order, one might point out that is much more than , and is itself much more than . In fact, is already less than.

Standard sequences for ordinal notations

To witness the fact that we have defined notations for ordinals below the Bachmann–Howard ordinal, we might define standard sequences converging to any one of them. Actually we will define canonical sequences for certain uncountable ordinals, too, namely the uncountable ordinals of countable cofinality which are representable.
The following rules are more or less obvious, except for the last:

First, get rid of the base representations: to define a standard sequence converging to, where is either or :
* if is zero then and there is nothing to be done;
* if is zero and is successor, then is successor and there is nothing to be done;
* if is limit, take the standard sequence converging to and replace in the expression by the elements of that sequence;
* if is successor and is limit, rewrite the last term as and replace the exponent in the last term by the elements of the fundamental sequence converging to it;
* if is successor and is also, rewrite the last term as and replace the last in this expression by the elements of the fundamental sequence converging to it.
If is, then take the obvious as the fundamental sequence for.
If then take as fundamental sequence for the sequence
If then take as fundamental sequence for the sequence
If where is a limit ordinal of countable cofinality, define the standard sequence for to be obtained by applying to the standard sequence for .
It remains to handle the case where with an ordinal of uncountable cofinality. Obviously it doesn't make sense to define a sequence converging to in this case; however, what we can define is a sequence converging to some with countable cofinality and such that is constant between and. This will be the first fixed point of a certain function. To find it, apply the same rules as to find the canonical sequence of, except that whenever a sequence converging to is called for, replace the in question, in the expression of, by a and perform a repeated iteration of the function : this gives a sequence tending to, and the canonical sequence for is,,... If we let the th element of the fundamental sequence for be denoted as, then we can state this more clearly using recursion. Using this notation, we can see that quite easily. We can define the rest of the sequence using recursion:.

Here are some examples for the last case:

The canonical sequence for is:,,... This indeed converges to after which is constant until.
The canonical sequence for is:,, This indeed converges to the value of at after which is constant until.
The canonical sequence for is: This converges to the value of at.
The canonical sequence for is This converges to the value of at.
The canonical sequence for is: This converges to the value of at.
The canonical sequence for is: This converges to the value of at.
The canonical sequence for is: This converges to the value of at.
The canonical sequence for is:

Here are some examples of the other cases:

The canonical sequence for is:,,,...
The canonical sequence for is:,,,...
The canonical sequence for is:,,,...
The canonical sequence for is:,,...
The canonical sequence for is:,,,...
The canonical sequence for is:,,,...
The canonical sequence for is:,,,...
The canonical sequence for is:,,....
The canonical sequence for is:,,....

Even though the Bachmann–Howard ordinal itself has no canonical notation, it is also useful to define a canonical sequence for it: this is,,...

A terminating process

Start with any ordinal less than or equal to the Bachmann–Howard ordinal, and repeat the following process so long as it is not zero:

if the ordinal is a successor, subtract one,
if it is a limit, replace it by some element of the canonical sequence defined for it.

Then it is true that this process always terminates ; however, like the hydra game:

it can take a very long time to terminate,
the proof of termination may be out of reach of certain weak systems of arithmetic.

To give some flavor of what the process feels like, here are some steps of it: starting from , we might go down to, from there down to, then then then then then then then and so on. It appears as though the expressions are getting more and more complicated whereas, in fact, the ordinals always decrease.
Concerning the first statement, one could introduce, for any ordinal less or equal to the Bachmann–Howard ordinal, the integer function which counts the number of steps of the process before termination if one always selects the 'th element from the canonical sequence. Then can be a very fast growing function: already is essentially, the function is comparable with the Ackermann function, and is comparable with the Goodstein function. If we instead make a function that satisfies the identity, so the index of the function increases it is applied, then we create a much faster growing function: is already comparable to the Goodstein function, and is comparable to the TREE function.
Concerning the second statement, a precise version is given by ordinal analysis: for example, Kripke–Platek set theory can prove that the process terminates for any given less than the Bachmann–Howard ordinal, but it cannot do this uniformly, i.e., it cannot prove the termination starting from the Bachmann–Howard ordinal. Some theories like Peano arithmetic are limited by much smaller ordinals.

Variations on the example

Making the function ''less'' powerful

It is instructive to make less powerful.
If we alter the definition of above to omit exponentiation from the repertoire from which is constructed, then we get , then and similarly, until we come to a fixed point which is then our. We then have and so on until. Since multiplication of 's is permitted, we can still form and and so on, but our construction ends there as there is no way to get at or beyond : so the range of this weakened system of notation is . This does not even go as far as the Feferman–Schütte ordinal.
If we alter the definition of yet some more to allow only addition as a primitive for construction, we get and and so on until and still. This time, and so on until and similarly. But this time we can go no further: since we can only add 's, the range of our system is.
If we alter the definition even more, to allow nothing except psi, we get,, and so on until,, and, at which point we can go no further since we cannot do anything with the 's. So the range of this system is only.
In both cases, we find that the limitation on the weakened function comes not so much from the operations allowed on the countable ordinals as on the uncountable ordinals we allow ourselves to denote.

Going beyond the Bachmann–Howard ordinal

We know that is the Bachmann–Howard ordinal. The reason why is no larger, with our definitions, is that there is no notation for . One could try to add the function to the allowed primitives beyond addition, multiplication and exponentiation, but that does not get us very far. To create more systematic notations for countable ordinals, we need more systematic notations for uncountable ordinals: we cannot use the function itself because it only yields countable ordinals, so the idea is to mimic its definition as follows:
Here, is a new ordinal guaranteed to be greater than all the ordinals which will be constructed using : again, letting and works.
For example,, and more generally for all countable ordinals and even beyond : this holds up to the first fixed point of the function beyond, which is the limit of, and so forth. Beyond this, we have and this remains true until : exactly as was the case for, we have and.
The function gives us a system of notations for the uncountable ordinals below, which is the limit of, and so forth.
Now we can reinject these notations in the original function, modified as follows:
This modified function coincides with the previous one up to — which is the Bachmann–Howard ordinal. But now we can get beyond this, and is . We have made our system doubly impredicative: to create notations for countable ordinals we use notations for certain ordinals between and which are themselves defined using certain ordinals beyond.
A variation on this scheme, which makes little difference when using just two collapsing functions, but becomes important for infinitely many of them, is to define
i.e., allow the use of only for arguments less than itself. With this definition, we must write instead of . This change is inessential because, intuitively speaking, the function collapses the nameable ordinals beyond below the latter so it matters little whether is invoked directly on the ordinals beyond or on their image by. But it makes it possible to define and by simultaneous induction, and this is important if we are to use infinitely many collapsing functions.
Indeed, there is no reason to stop at two levels: using new cardinals in this way,, we get a system essentially equivalent to that introduced by Buchholz, the inessential difference being that since Buchholz uses ordinals from the start, he does not need to allow multiplication or exponentiation; also, Buchholz does not introduce the numbers or in the system as they will also be produced by the functions: this makes the entire scheme much more elegant and more concise to define, albeit more difficult to understand. This system is also sensibly equivalent to the earlier "ordinal diagrams" of Takeuti and functions of Feferman: their range is the same.

A "normal" variant

Most definitions of ordinal collapsing functions found in the recent literature differ from the ones we have given in one technical but important way which makes them technically more convenient although intuitively less transparent. We now explain this.
The following definition is completely equivalent to that of the function above:
We can now make a change to the definition which makes it subtly different:
The first values of coincide with those of : namely, for all where, we have because the additional clause is always satisfied. But at this point the functions start to differ: while the function gets "stuck" at for all, the function satisfies because the new condition imposes. On the other hand, we still have . Note in particular that, unlike, is not monotonic, nor is it continuous.
Despite these changes, the function also defines a system of ordinal notations up to the Bachmann–Howard ordinal: the notations, and the conditions for canonicity, are slightly different.

Other similar ordinal collapsing functions

Arai's ''ψ''

Arai's ψ function is an ordinal collapsing function introduced by Toshiyasu Arai in his paper: A simplified ordinal analysis of first-order reflection. is a collapsing function such that, where represents the first uncountable ordinal. Throughout the course of this article, represents Kripke–Platek set theory for a -reflecting universe, is the least -indescribable cardinal, is a fixed natural number, and.
Suppose for a -sentence. Then, there exists a finite such that for,. It can also be proven that proves that each initial segment is well-founded, and therefore, is the proof-theoretic ordinal of. One can then make the following conversions:

, where is either the least recursively regular ordinal or the least uncountable cardinal, is Kripke–Platek set theory with infinity and is the Bachmann–Howard ordinal.
, where is either the least limit of admissible ordinals or the least limit of infinite cardinals and is Buchholz's ordinal.
, where is either the least limit of admissible ordinals or the least limit of infinite cardinals, is KPi without the collection scheme and is the Takeuti–Feferman–Buchholz ordinal.
, where is either the least recursively inaccessible ordinal or the least weakly inaccessible cardinal and is Kripke–Platek set theory with a recursively inaccessible universe.

Bachmann's ''ψ''

The first true ordinal collapsing function, Bachmann's was invented by Heinz Bachmann, somewhat cumbersome as it depends on fundamental sequences for all limit ordinals; and the original definition is complicated. Michael Rathjen has suggested a "recast" of the system, which goes like so:

Let represent an uncountable ordinal such as ;
Then define as the closure of under addition, and for.
is the smallest countable ordinal ρ such that

is the Bachmann–Howard ordinal, the proof-theoretic ordinal of Kripke–Platek set theory with the axiom of infinity.

Buchholz's ''ψ''

Buchholz's is a hierarchy of single-argument functions, with occasionally abbreviated as. This function is likely the most well known out of all ordinal collapsing functions. The definition is so:

Define and for.
Let be the set of distinct terms in the Cantor normal form of

The limit of this system is, the Takeuti–Feferman–Buchholz ordinal.

Extended Buchholz's ''ψ''

This ordinal collapsing function is a sophisticated extension of Buchholz's by mathematician Denis Maksudov. The limit of this system, sometimes called the Extended Buchholz Ordinal, is much greater, equal to where denotes the first omega fixed point. The function is defined as follows:

Define and for.

Madore's ''ψ''

This ordinal collapsing function was the same as the ψ function previously used throughout this article; it is a simpler, more efficient version of Buchholz's ψ function defined by David Madore. Its use in this article lead to widespread use of the function.
This function was used by Chris Bird, who also invented the next ordinal collapsing function.

Bird's θ

Chris Bird devised the following shorthand for the extended Veblen function :

is abbreviated

This function is only defined for arguments less than, and its outputs are limited by the small Veblen ordinal.

Jäger's ''ψ''

Jäger's ψ is a hierarchy of single-argument ordinal functions ψ_κ indexed by uncountable regular cardinals κ smaller than the least weakly Mahlo cardinal M₀ introduced by German mathematician Gerhard Jäger in 1984. It was developed on the base of Buchholz's approach.

If for some α < κ,.
If for some α, β < κ,.
For every finite n, is the smallest set satisfying the following:
* The sum of any finitely many ordinals in belongs to.
* For any,.
* For any,.
* For any ordinal γ and uncountable regular cardinal,.
* For any and uncountable regular cardinal,.

Simplified Jäger's ''ψ''

This is a sophisticated simplification of Jäger's ψ created by Denis Maksudov. An ordinal is α-weakly inaccessible if it is uncountable, regular and it is a limit of γ-weakly inaccessible cardinals for γ < α. Let I be the first α-weakly inaccessible cardinal, I be the first α-weakly inaccessible cardinal after I and I = for limit β. Restrict ρ and to uncountable regular ordinals of the form I or I. Then,
*

Rathjen's ''Ψ''

Rathjen's Ψ function is based on the least weakly compact cardinal to create large countable ordinals. For a weakly compact cardinal K, the functions,,, and are defined in mutual recursion in the following way:

M⁰ =, where Lim denotes the class of limit ordinals.
For α > 0, M^α is the set is stationary in
is the closure of under addition,, given ξ < K, given ξ < α, and given.
.
For,.

Collapsing large cardinals

As noted in the introduction, the use and definition of ordinal collapsing functions is strongly connected with the theory of ordinal analysis, so the collapse of this or that large cardinal must be mentioned simultaneously with the theory for which it provides a proof-theoretic analysis.

Gerhard Jäger and Wolfram Pohlers described the collapse of an inaccessible cardinal to describe the ordinal-theoretic strength of Kripke–Platek set theory augmented by the recursive inaccessibility of the class of ordinals, which is also proof-theoretically equivalent to -comprehension plus bar induction. Roughly speaking, this collapse can be obtained by adding the function itself to the list of constructions to which the collapsing system applies.
Michael Rathjen then described the collapse of a Mahlo cardinal to describe the ordinal-theoretic strength of Kripke–Platek set theory augmented by the recursive Mahloness of the class of ordinals.
Rathjen later described the collapse of a weakly compact cardinal to describe the ordinal-theoretic strength of Kripke–Platek set theory augmented by certain reflection principles. Very roughly speaking, this proceeds by introducing the first cardinal which is -hyper-Mahlo and adding the function itself to the collapsing system.
In a 2015 paper, Toshiyasu Arai has created ordinal collapsing functions for a vector of ordinals, which collapse -indescribable cardinals for. These are used to carry out ordinal analysis of Kripke–Platek set theory augmented by -reflection principles.
Rathjen has investigated the collapse of yet larger cardinals, with the ultimate goal of achieving an ordinal analysis of -comprehension.