Wikipedia / Ordinal collapsing function
Wikipedia / Ordinal collapsing function
In mathematical logic and set theory, an ordinal collapsing function (or projection function) is a technique for defining (notations for) 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 (though they can be replaced with recursively large ordinals at the cost of extra technical difficulty), 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 (i.e., defining a system of notations up to 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 (such as those seen in reverse mathematics), extensions of Kripke–Platek set theory, Bishop-style systems of constructive mathematics or Martin-Löf-style systems of intuitionistic type theory.
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 is described when going beyond the Bachmann–Howard ordinal.
Definition
stand for the first uncountable ordinal, or, in fact, any ordinal that is an \varepsilon-number and guaranteed to be greater than all the countable ordinals that will be constructed (for example, the Church–Kleene ordinal because it allows the convenient use of the word countable in the definitions).
(which will be non-decreasing and continuous, as follows:
.
by recursively applying the following functions: ordinal addition, multiplication and exponentiation.)
.
In a more concise (although more obscure) way:
).
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 will "collapse" them to countable ordinals.
Computation of values of ψ
is able to produce notations for certain ordinals, we now compute its first values.
Predicative start
. The first ordinal that it does not contain is \varepsilon_0 and so on .
. We therefore have:
.
functions are the Veblen functions.)
for some time:
.
First impredicative values
function ).
are impredicative).
Values of ψ up to the Feferman–Schütte ordinal
.
.
, which is the Feferman–Schütte ordinal is the Feferman–Schütte ordinal.
Beyond the Feferman–Schütte ordinal
). In this manner:
is the Ackermann ordinal defined predicatively),
is the "small" Veblen ordinal defined predicatively using finitely many variables),
is the "large" Veblen ordinal defined predicatively using transfinitely-but-predicatively-many variables),
, etc., is the Bachmann–Howard ordinal is constant, and we can go no further with the definition we have given.
Ordinal notations up to the Bachmann–Howard ordinal
function defines notations for ordinals up to the Bachmann–Howard ordinal.
A note about base representations
is a natural number representation" is an obvious generalization of the Cantor normal form).
and repeat the operation until the process terminates (any decreasing sequence of ordinals is finite). We call the resulting expression the representation and the various coefficients involved (including as exponents) the pieces.
Some properties of ψ
is non-decreasing and continuous (this is more or less obvious from its definition).
is the closure, so they are equal.
). Indeed, if it were not, then by writing it in Cantor normal form, a contradiction.
-pieces (defined above, which was to be shown.
).
is the least upper bound .
.
The ordinal notation
.
, so we are finished.
be the greatest (so we have already defined a notation for it). If this is not.
Note function (which may be uncountable).
Examples
, the canonical ordinal notation defined coincides with the iterated Cantor normal form (by definition).
(and write the pieces of that-number base which gives a non-trivial representation.
-number base which gives a non-trivial representation.
is equal to the Bachmann–Howard ordinal, this is not a "canonical notation" in the sense we have defined (canonical notations are defined only for ordinals less than the Bachmann–Howard ordinal).
Conditions for canonicalness
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 always trumps the lesser or even arbitrary sums, products and exponentials of the lesser).
.
.
Standard sequences for ordinal notations
To witness the fact that we have defined notations for ordinals below the Bachmann–Howard ordinal (which are all of countable cofinality), we might define standard sequences converging to any one of them (provided it is a limit ordinal, of course). Actually we will define canonical sequences for certain uncountable ordinals, too, namely the uncountable ordinals of countable-pieces are less than the Bachmann–Howard ordinal).
The following rules are more or less obvious, except for the last:
, but see below):
and there is nothing to be done;
is successor and there is nothing to be done;
in the expression by the elements of that sequence;
in the last term by the elements of the fundamental sequence converging to it;
in this expression by the elements of the fundamental sequence converging to it.
.
is a limit ordinal of countable is continuous and increasing, here).
an ordinal of uncountable. (The examples below should make this clearer.)
Here are some examples for the last (and most interesting) case:
.
.
.
.
.
.
.
Here are some examples of the other cases:
...
...
...
...
...
...
...
).
, which was given above).
...
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 (that is, replace it with its predecessor),
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 (as any decreasing sequence of ordinals is finite); however, like (but even more so than for) 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.
and so on. It appears as though the expressions are getting more and more complicated whereas, in fact, the ordinals always decrease.
, the integer is comparable with the Ackermann function is comparable with the Goodstein function 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 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 in the case of Peano arithmetic).
Variations on the example
Making the function less powerful
less powerful.
is the same in our weaker system as in our original system, except that now we cannot go beyond it). This does not even go as far as the Feferman–Schütte ordinal.
.
.
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
), so the idea is to mimic its definition as follows:
).
works.
.
function gives us a system of notations (assuming and so forth.
function, modified as follows:
).
-number after the Bachmann–Howard ordinal). We have made our system doubly.
A variation on this scheme, which makes little difference when using just two (or finitely many) collapsing functions, but becomes important for infinitely many of them, is to define
).
by simultaneous (rather than "downward") induction, and this is important if we are to use infinitely many collapsing functions.
, we get a system essentially equivalent to that introduced by Buchholz, 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 (and much more difficult to grasp) "ordinal diagrams" of Takeuti, which could be called the Takeuti-Feferman–Buchholz ordinal, and which describes the strength of \Pi^1_1-comprehension plus bar induction).
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.
.
.)
We can now make a change to the definition which makes it subtly different:
.
, is not monotonic, nor is it continuous.
).
Other similar ordinal collapsing functions
Arai's ψ
Arai's ψ function is an ordinal collapsing function introduced by Toshiyasu Arai (husband of Noriko H. Arai) in his paper: A simplified ordinal analysis of first-order reflection represents the first uncountable ordinal (it can be replaced by the Church–Kleene ordinal represents Kripke–Platek set theory.
. Then, there exists is well-founded is the proof-theoretic ordinal. One can then make the following conversions:
is Kripke–Platek set theory is the Bachmann–Howard ordinal.
is Kripke–Platek set theory with a recursively inaccessible universe.
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:
;
.
is the Bachmann–Howard ordinal, the proof-theoretic ordinal of Kripke–Platek set theory with the axiom of infinity (KP).
Buchholz's ψ
. This function is likely the most well known out of all ordinal collapsing functions. The definition is so:
.
, see Cantor normal form theorem)
, the Takeuti–Feferman–Buchholz ordinal.
Extended Buchholz's ψ
denotes the first omega fixed point. The function is defined as follows:
.
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 θ
:
, 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 M0 introduced by German mathematician Gerhard Jäger in 1984. It was developed on the base of Buchholz's approach.
for some α < κ.
for some α, β <κ.
For every finite n is the smallest set satisfying the following:
.
.
.
For any ordinal γ 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(α, 0) be the first α-weakly inaccessible cardinal, I(α, β + 1) be the first α-weakly inaccessible cardinal after I(α, β) and I(α, β for limit β. Restrict to uncountable regular ordinals of the form I(α, 0) or I(α, β + 1). Then,
Rathjen's Ψ
Rathjen's Ψ are defined in mutual recursion in the following way:
M0, where Lim denotes the class of limit ordinals.
For α > 0, Mα
.
.
.
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 (KPi), which is also proof-theoretically equivalent-comprehension plus bar induction 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 (KPM).
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 function itself to the collapsing system.
-indescribable cardinals. These are used to carry out ordinal analysis-reflection principles.
-separation).
Notes
References
(slides of a talk given at Fischbachau)