In
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
and
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concer ...
, an ordinal collapsing function (or projection function) is a technique for defining (
notations
''Notations'' is a book that was edited and compiled by American avant-garde composer John Cage (1912–1992) with Alison Knowles and first published in 1969 by Something Else Press. The book is made up of a large collection of graphical scores, ...
for) certain
recursive
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathemati ...
large countable ordinal
In the mathematical discipline of set theory, there are many ways of describing specific countable set, countable ordinal number, ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond ...
s, whose principle is to give names to certain ordinals much larger than the one being defined, perhaps even
large cardinals
In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least � ...
(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
In mathematics, logic and philosophy of mathematics, something that is impredicative is a self-referencing definition. Roughly speaking, a definition is impredicative if it invokes (mentions or quantifies over) the set being defined, or (more co ...
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
In mathematics, the Bachmann–Howard ordinal (also known as the Howard ordinal, or Howard-Bachmann ordinal) is a large countable ordinal.
It is the proof-theoretic ordinal of several mathematical theories, such as Kripke–Platek set theory (w ...
(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
In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength.
If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory ha ...
, since the large countable ordinals defined and denoted by a given collapse are used to describe the ordinal-theoretic strength of certain
formal system
A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system.
A for ...
s, typically
[Rathjen, 1995 (Bull. Symbolic Logic)][Kahle, 2002 (Synthese)] subsystems of
analysis
Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (3 ...
(such as those seen in the light of
reverse mathematics
Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in cont ...
), extensions of
Kripke–Platek set theory
The Kripke–Platek set theory (KP), pronounced , is an axiomatic set theory developed by Saul Kripke and Richard Platek.
The theory can be thought of as roughly the predicative part of ZFC and is considerably weaker than it.
Axioms
In its fo ...
,
Bishop
A bishop is an ordained clergy member who is entrusted with a position of authority and oversight in a religious institution.
In Christianity, bishops are normally responsible for the governance of dioceses. The role or office of bishop is ...
-style systems of
constructive mathematics
In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a specific example of a mathematical object in order to prove that an example exists. Contrastingly, in classical mathematics, one can prove t ...
or
Martin-Löf-style systems of
intuitionistic type theory
Intuitionistic type theory (also known as constructive type theory, or Martin-Löf type theory) is a type theory and an alternative foundation of mathematics.
Intuitionistic type theory was created by Per Martin-Löf, a Swedish mathematician and p ...
.
(
psi
Psi, PSI or Ψ may refer to:
Alphabetic letters
* Psi (Greek) (Ψ, ψ), the 23rd letter of the Greek alphabet
* Psi (Cyrillic) (Ѱ, ѱ), letter of the early Cyrillic alphabet, adopted from Greek
Arts and entertainment
* "Psi" as an abbreviation ...
)(1)
Ordinal collapsing functions are typically denoted using some variation of either the Greek letter
(
psi
Psi, PSI or Ψ may refer to:
Alphabetic letters
* Psi (Greek) (Ψ, ψ), the 23rd letter of the Greek alphabet
* Psi (Cyrillic) (Ѱ, ѱ), letter of the early Cyrillic alphabet, adopted from Greek
Arts and entertainment
* "Psi" as an abbreviation ...
) or
(
theta
Theta (, ; uppercase: Θ or ; lowercase: θ or ; grc, ''thē̂ta'' ; Modern: ''thī́ta'' ) is the eighth letter of the Greek alphabet, derived from the Phoenician letter Teth . In the system of Greek numerals, it has a value of 9.
...
).
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
[Buchholz, 1986 (Ann. Pure Appl. Logic)] 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
Below may refer to:
*Earth
* Ground (disambiguation)
* Soil
* Floor
* Bottom (disambiguation)
* Less than
*Temperatures below freezing
* Hell or underworld
People with the surname
* Ernst von Below (1863–1955), German World War I general
* Fr ...
.
Definition
Let
stand for the
first uncountable ordinal
In mathematics, the first uncountable ordinal, traditionally denoted by \omega_1 or sometimes by \Omega, is the smallest ordinal number that, considered as a set, is uncountable. It is the supremum (least upper bound) of all countable ordinals. ...
, or, in fact, any ordinal which is an
-number and guaranteed to be greater than all the
countable ordinal
In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets.
A finite set can be enumerated by successively labeling each element with the lea ...
s which will be constructed (for example, the
Church–Kleene ordinal
In mathematics, particularly set theory, non-recursive ordinals are large countable ordinals greater than all the recursive ordinals, and therefore can not be expressed using ordinal collapsing functions.
The Church–Kleene ordinal and variant ...
is adequate for our purposes; but we will work with
because it allows the convenient use of the word ''countable'' in the definitions).
We define a function
(which will be
non-decreasing
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called t ...
and
continuous
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous g ...
), taking an arbitrary ordinal
to a countable ordinal
, recursively on
, as follows:
:Assume
has been defined for all
, and we wish to define
.
:Let
be the set of ordinals generated starting from
,
,
and
by recursively applying the following functions: ordinal
addition, multiplication and exponentiation and the function
, i.e., the restriction of
to ordinals
. (Formally, we define
and inductively
for all natural numbers
and we let
be the union of the
for all
.)
:Then
is defined as the smallest ordinal not belonging to
.
In a more concise (although more obscure) way:
:
is the smallest ordinal which cannot be expressed from
,
,
and
using sums, products, exponentials, and the
function itself (to previously constructed ordinals less than
).
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 which 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 (beyond
, that is); 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 which it does not contain is
(which is the limit of
,
,
and so on — less than
by assumption). The upper bound of the ordinals it contains is
(the limit of
,
,
and so on), 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:
:
for all
, where
is the smallest fixed point of
.
(Here, the
functions are the
Veblen function
In mathematics, the Veblen functions are a hierarchy of normal functions ( continuous strictly increasing functions from ordinals to ordinals), introduced by Oswald Veblen in . If φ0 is any normal function, then for any non-zero ordinal α, φ ...
s defined starting with
.)
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:
:
for all
.
First impredicative values
Again,
. However, when we come to computing
, something has changed: since
was ("artificially") 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
(the smallest
-number after
).
We say that the definition
and the next values of the function
such as
are
impredicative
In mathematics, logic and philosophy of mathematics, something that is impredicative is a self-referencing definition. Roughly speaking, a definition is impredicative if it invokes (mentions or quantifies over) the set being defined, or (more co ...
because they use ordinals (here,
) greater than the ones which are being defined (here,
).
Values of ''ψ'' up to the Feferman–Schütte ordinal
The fact that
remains true for all
(note, in particular, that
: but since now the ordinal
has been constructed there is nothing to prevent from going beyond this). However, at
(the first fixed point of
beyond
), 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
In mathematics, the Feferman–Schütte ordinal Γ0 is a large countable ordinal.
It is the proof-theoretic ordinal of several mathematical theories, such as arithmetical transfinite recursion.
It is named after Solomon Feferman and Kurt Schüt ...
. 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 (which can also be noted
using the many-valued Veblen functions) we have
, until the first fixed point
of the
itself, which will be
(and the first fixed point
of the
functions will be
). In this manner:
*
is the
Ackermann ordinal
In mathematics, the Ackermann ordinal is a certain large countable ordinal, named after Wilhelm Ackermann. The term "Ackermann ordinal" is also occasionally used for the small Veblen ordinal, a somewhat larger ordinal.
Unfortunately there ...
(the range of the notation
defined predicatively),
*
is the
"small" Veblen ordinal (the range of the notations
predicatively using finitely many variables),
*
is the
"large" Veblen ordinal (the range of the notations
predicatively using transfinitely-but-predicatively-many variables),
* the limit
of
,
,
, etc., is the
Bachmann–Howard ordinal
In mathematics, the Bachmann–Howard ordinal (also known as the Howard ordinal, or Howard-Bachmann ordinal) is a large countable ordinal.
It is the proof-theoretic ordinal of several mathematical theories, such as Kripke–Platek set theory (w ...
: 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 which is a power of
(for example
itself, or
, or
), any ordinal
can be uniquely expressed in the form
, where
is a natural number,
are non-zero ordinals less than
, and
are ordinal numbers (we allow
). This "base
representation" is an obvious generalization of the
Cantor normal form
In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an exp ...
(which is the case
). 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 (i.e.,
, in which case
and
).
If
is an ordinal less than
, then its base
representation has coefficients
(by definition) and exponents
(because of the assumption
): hence one can rewrite these exponents in base
and repeat the operation until the process terminates (any decreasing sequence of ordinals is finite). We call the resulting expression the ''iterated base
representation'' of
and the various coefficients involved (including as exponents) the ''pieces'' of the representation (they are all
), or, for short, the
-pieces of
.
Some properties of ''ψ''
* The function
is non-decreasing and continuous (this is more or less obvious from its definition).
* If
with
then necessarily
. Indeed, no ordinal
with
can belong to
(otherwise its image by
, which is
would belong to
— impossible); so
is closed by everything under which
is the closure, so they are equal.
* Any value
taken by
is an
-number (i.e., a fixed point of
). Indeed, if it were not, then by writing it in
Cantor normal form
In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an exp ...
, 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 (defined
above) 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 (because
is an
-number, so ordinals less than it are 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,
(indeed, the lemma shows that
).
* Any
-number less than some element in the range of
is itself in the range of
(that is,
omits no
-number). 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
(less than
) all of whose
-pieces are less than
. Indeed, we know that all ordinals less than
, hence all ordinals (less than
) whose
-pieces are less than
, are in
. Conversely, if we assume
for all
(in other words if
is the least possible with
), 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 (canonical) 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
(this is because the set of
-numbers is closed): 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 (possibly uncountable) ordinal
: let
be the ''greatest'' possible such ordinal (which exists since
is continuous). We use the iterated base
representation of
: it remains to show that every piece of this representation is less than
(so we have already defined a notation for it). If this is ''not'' the case then, by the properties we have shown,
does not contain
; but then
(they are closed under the same operations, since the value of
at
can never be taken), 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 (viz.: write them in iterated base
representation and use the canonical representation for every piece). This canonical notation is used for arguments of the
function (which may be uncountable).
Examples
For ordinals less than
, the canonical ordinal notation defined coincides with the iterated Cantor normal form (by definition).
For ordinals less than
, the notation coincides with iterated base
notation (the pieces being themselves written in iterated Cantor normal form): 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
(and write the pieces of ''that'' in iterated Cantor normal form): 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 (canonical notations are defined only for ordinals ''less'' than the Bachmann–Howard ordinal).
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 (this is a consequence of the fact that the
-pieces of
, where
is the largest possible such that
for some
-number
, are all less than
, as we have shown above). For example,
does not occur as a notation: it is a well-defined expression (and it is equal to
since
is constant between
and
), 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 (keeping in mind that
is greater than any expression obtained by
, and for canonical values the greater
always trumps the lesser or even arbitrary sums, products and exponentials of the lesser).
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
(the Feferman–Schütte ordinal) is much more than
(because
is greater than
of anything), and
is itself much more than
(because
is greater than
, so any sum-product-or-exponential expression involving
and smaller value will remain less 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 (which are all of countable
cofinality
In mathematics, especially in order theory, the cofinality cf(''A'') of a partially ordered set ''A'' is the least of the cardinalities of the cofinal subsets of ''A''.
This definition of cofinality relies on the axiom of choice, as it uses t ...
), 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'' cofinality (if we are to hope to define a sequence converging to them...) which are representable (that is, all of whose
-pieces are less than the Bachmann–Howard ordinal).
The following rules are more or less obvious, except for the last:
* First, get rid of the (iterated) base
representations: to define a standard sequence converging to
, where
is either
or
(or
, but see below):
** 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
(recall that
is continuous and increasing, here).
* It remains to handle the case where
with
an ordinal of ''uncountable'' cofinality (e.g.,
itself). 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 (continuous and non-decreasing) function
. To find it, apply the same rules (from the base
representation of
) as to find the canonical sequence of
, except that whenever a sequence converging to
is called for (something which cannot exist), replace the
in question, in the expression of
, by a
(where
is a variable) and perform a repeated iteration (starting from
, say) of the function
: this gives a sequence
tending to
, and the canonical sequence for
is
,
,
... If we let the
th element (starting at
) of the fundamental sequence for
be denoted as
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
In mathematics, specifically in graph theory and number theory, a hydra game is a single-player iterative mathematical game played on a mathematical tree called a ''hydra'' where, usually, the goal is to cut off the hydra's "heads" while the hyd ...
:
# 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
\psi(\Omega^) (the small Veblen ordinal), we might go down to
\psi(\Omega^), from there down to
\psi(\Omega^), then
\psi(\Omega^) then
\psi(\Omega^) then
\psi(\Omega^) then
\psi(\Omega^) then
\psi(\Omega^) then
\psi(\Omega^) then
\psi(\Omega^) 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
\alpha less or equal to the Bachmann–Howard ordinal
\psi(\varepsilon_), the integer function
f_\alpha(n) which counts the number of steps of the process before termination if one always selects the
n'th element from the canonical sequence (this function satisfies the identity
f_\alpha(n) = f_(n) + 1). Then
f_\alpha can be a very fast growing function: already
f_(n) is essentially
n^n, the function
f_(n) is comparable with the
Ackermann function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive. All primitive recursive functions are total ...
A(n,n), and
f_(n) is comparable with the
Goodstein function
In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every ''Goodstein sequence'' eventually terminates at 0. Kirby and Paris showed that it is unprovable in P ...
. If we instead make a function that satisfies the identity
g_\alpha(n) = g_(n+1) + 1, so the index of the function increases it is applied, then we create a much faster growing function:
g_(n) is already comparable to the Goodstein function, and
g_(n) is comparable to the
TREE
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
function.
Concerning the second statement, a precise version is given by
ordinal analysis
In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength.
If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory ha ...
: for example,
Kripke–Platek set theory
The Kripke–Platek set theory (KP), pronounced , is an axiomatic set theory developed by Saul Kripke and Richard Platek.
The theory can be thought of as roughly the predicative part of ZFC and is considerably weaker than it.
Axioms
In its fo ...
can prove
[Rathjen, 2005 (Fischbachau slides)] that the process terminates for any given
\alpha 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 mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
are limited by much smaller ordinals (
\varepsilon_0 in the case of Peano arithmetic).
Variations on the example
Making the function ''less'' powerful
It is instructive (although not exactly useful) to make
\psi less powerful.
If we alter the definition of
\psi above to omit exponentiation from the repertoire from which
C(\alpha) is constructed, then we get
\psi(0) = \omega^\omega (as this is the smallest ordinal which cannot be constructed from
0,
1 and
\omega using addition and multiplication only), then
\psi(1) = \omega^ and similarly
\psi(\omega) = \omega^,
\psi(\psi(0)) = \omega^ until we come to a fixed point which is then our
\psi(\Omega) = \varepsilon_0. We then have
\psi(\Omega+1) = ^\omega and so on until
\psi(\Omega 2) = \varepsilon_1. Since multiplication of
\Omega's is permitted, we can still form
\psi(\Omega^2) = \varphi_2(0) and
\psi(\Omega^3) = \varphi_3(0) and so on, but our construction ends there as there is no way to get at or beyond
\Omega^\omega: so the range of this weakened system of notation is
\psi(\Omega^\omega) = \phi_\omega(0) (the value of
\psi(\Omega^\omega) 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.
If we alter the definition of
\psi yet some more to allow only addition as a primitive for construction, we get
\psi(0) = \omega^2 and
\psi(1) = \omega^3 and so on until
\psi(\psi(0)) = \omega^ and still
\psi(\Omega) = \varepsilon_0. This time,
\psi(\Omega+1) = \varepsilon_0 \omega and so on until
\psi(\Omega 2) = \varepsilon_1 and similarly
\psi(\Omega 3) = \varepsilon_2. But this time we can go no further: since we can only add
\Omega's, the range of our system is
\psi(\Omega\omega) = \varepsilon_\omega = \varphi_1(\omega).
In both cases, we find that the limitation on the weakened
\psi 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
\psi(\varepsilon_) is the Bachmann–Howard ordinal. The reason why
\psi(\varepsilon_+1) is no larger, with our definitions, is that there is no notation for
\varepsilon_ (it does not belong to
C(\alpha) for any
\alpha, it is always the least upper bound of it). One could try to add the
\varepsilon function (or the Veblen functions of so-many-variables) 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
\psi function itself because it only yields countable ordinals (e.g.,
\psi(\Omega+1) is,
\varepsilon_, certainly not
\varepsilon_), so the idea is to mimic its definition as follows:
:Let
\psi_1(\alpha) be the smallest ordinal which cannot be expressed from all countable ordinals and
\Omega_2 using sums, products, exponentials, and the
\psi_1 function itself (to previously constructed ordinals less than
\alpha).
Here,
\Omega_2 is a new ordinal guaranteed to be greater than all the ordinals which will be constructed using
\psi_1: again, letting
\Omega = \omega_1 and
\Omega_2 = \omega_2 works.
For example,
\psi_1(0) = \Omega, and more generally
\psi_1(\alpha) = \varepsilon_ for all countable ordinals and even beyond (
\psi_1(\Omega) = \psi_1(\psi_1(0)) = \varepsilon_ and
\psi_1(\psi_1(1)) = \varepsilon_): this holds up to the first fixed point
\zeta_ of the function
\xi\mapsto\varepsilon_\xi beyond
\Omega, which is the limit of
\psi_1(0),
\psi_1(\psi_1(0)) and so forth. Beyond this, we have
\psi_1(\alpha) = \zeta_ and this remains true until
\Omega_2: exactly as was the case for
\psi(\Omega), we have
\psi_1(\Omega_2) = \zeta_ and
\psi_1(\Omega_2+1) = \varepsilon_.
The
\psi_1 function gives us a system of notations (''assuming'' we can somehow write down all countable ordinals!) for the uncountable ordinals below
\psi_1(\varepsilon_), which is the limit of
\psi_1(\Omega_2),
\psi_1(^) and so forth.
Now we can reinject these notations in the original
\psi function, modified as follows:
:
\psi(\alpha) is the smallest ordinal which cannot be expressed from
0,
1,
\omega,
\Omega and
\Omega_2 using sums, products, exponentials, the
\psi_1 function, and the
\psi function itself (to previously constructed ordinals less than
\alpha).
This modified function
\psi coincides with the previous one up to (and including)
\psi(\psi_1(1)) — which is the Bachmann–Howard ordinal. But now we can get beyond this, and
\psi(\psi_1(1)+1) is
\varepsilon_ (the next
\varepsilon-number after the Bachmann–Howard ordinal). We have made our system ''doubly'' impredicative: to create notations for countable ordinals we use notations for certain ordinals between
\Omega and
\Omega_2 which are themselves defined using certain ordinals beyond
\Omega_2.
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
:
\psi(\alpha) is the smallest ordinal which cannot be expressed from
0,
1,
\omega,
\Omega and
\Omega_2 using sums, products, exponentials, and the
\psi_1 and
\psi function (to previously constructed ordinals less than
\alpha).
i.e., allow the use of
\psi_1 only for arguments less than
\alpha itself. With this definition, we must write
\psi(\Omega_2) instead of
\psi(\psi_1(\Omega_2)) (although it is still also equal to
\psi(\psi_1(\Omega_2)) = \psi(\zeta_), of course, but it is now constant until
\Omega_2). This change is inessential because, intuitively speaking, the
\psi_1 function collapses the nameable ordinals beyond
\Omega_2 below the latter so it matters little whether
\psi is invoked directly on the ordinals beyond
\Omega_2 or on their image by
\psi_1. But it makes it possible to define
\psi and
\psi_1 by ''simultaneous'' (rather than "downward") 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
\omega+1 new cardinals in this way,
\Omega_1,\Omega_2,\ldots,\Omega_\omega, we get a system essentially equivalent to that introduced by Buchholz,
[ the inessential difference being that since Buchholz uses \omega+1 ordinals from the start, he does not need to allow multiplication or exponentiation; also, Buchholz does not introduce the numbers 1 or \omega in the system as they will also be produced by the \psi 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 and \theta functions of Feferman: their range is the same (\psi_0(\varepsilon_), which could be called the Takeuti-Feferman–Buchholz ordinal, and which describes the ]strength
Strength may refer to:
Physical strength
*Physical strength, as in people or animals
*Hysterical strength, extreme strength occurring when people are in life-and-death situations
*Superhuman strength, great physical strength far above human ca ...
of \Pi^1_1-comprehension plus bar induction Bar induction is a reasoning principle used in intuitionistic mathematics, introduced by L. E. J. Brouwer. Bar induction's main use is the intuitionistic derivation of the fan theorem, a key result used in the derivation of the uniform continuity ...
).
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 (by induction on \alpha) is completely equivalent to that of the function \psi above:
:Let C(\alpha,\beta) be the set of ordinals generated starting from 0, 1, \omega, \Omega and all ordinals less than \beta by recursively applying the following functions: ordinal addition, multiplication and exponentiation, and the function \psi\upharpoonright_\alpha. Then \psi(\alpha) is defined as the smallest ordinal \rho such that C(\alpha,\rho) \cap \Omega = \rho.
(This is equivalent, because if \sigma is the smallest ordinal not in C(\alpha,0), which is how we originally defined \psi(\alpha), then it is also the smallest ordinal not in C(\alpha,0) = C(\alpha,\sigma), and furthermore the properties we described of \psi imply that no ordinal between \sigma inclusive and \Omega exclusive belongs to C(\alpha,\sigma).)
We can now make a change to the definition which makes it subtly different:
:Let \tilde C(\alpha,\beta) be the set of ordinals generated starting from 0, 1, \omega, \Omega and all ordinals less than \beta by recursively applying the following functions: ordinal addition, multiplication and exponentiation, and the function \tilde\psi\upharpoonright_\alpha. Then \tilde\psi(\alpha) is defined as the smallest ordinal \rho such that \tilde C(\alpha,\rho) \cap \Omega = \rho and \alpha \in \tilde C(\alpha,\rho).
The first values of \tilde\psi coincide with those of \psi: namely, for all \alpha<\zeta_0 where \zeta_0 = \varphi_2(0), we have \tilde\psi(\alpha) = \psi(\alpha) because the additional clause \alpha \in \tilde C(\alpha,\rho) is always satisfied. But at this point the functions start to differ: while the function \psi gets "stuck" at \zeta_0 for all \zeta_0 \leq \alpha \leq \Omega, the function \tilde\psi satisfies \tilde\psi(\zeta_0) = \varepsilon_ because the new condition \alpha \in \tilde C(\alpha,\rho) imposes \tilde\psi(\zeta_0) > \zeta_0. On the other hand, we still have \tilde\psi(\Omega) = \zeta_0 (because \Omega \in C(\alpha,\rho) for all \rho so the extra condition does not come in play). Note in particular that \tilde\psi, unlike \psi, is not monotonic, nor is it continuous.
Despite these changes, the \tilde\psi function also defines a system of ordinal notations up to the Bachmann–Howard ordinal: the notations, and the conditions for canonicity, are slightly different (for example, \psi(\Omega+1+\alpha) = \tilde\psi(\tilde\psi(\Omega)+\alpha) for all \alpha less than the common value \psi(\Omega2) = \tilde\psi(\Omega+1)).
Other similar OCFs
Arai's ''ψ''
Arai's ''ψ'' function is an ordinal collapsing function introduced by Toshiyasu Arai (husband of Noriko H. Arai
Noriko H. Arai ( ja, 新井紀子, born 1962) is a Japanese researcher in mathematical logic and artificial intelligence, known for her work on a project to develop robots that can pass the entrance examinations for the University of Tokyo. She is ...
) in his paper: ''A simplified ordinal analysis of first-order reflection''. \psi_\Omega(\alpha) is a collapsing function such that \psi_\Omega(\alpha) < \Omega, where \Omega represents the first uncountable ordinal
In mathematics, the first uncountable ordinal, traditionally denoted by \omega_1 or sometimes by \Omega, is the smallest ordinal number that, considered as a set, is uncountable. It is the supremum (least upper bound) of all countable ordinals. ...
(it can be replaced by the Church–Kleene ordinal
In mathematics, particularly set theory, non-recursive ordinals are large countable ordinals greater than all the recursive ordinals, and therefore can not be expressed using ordinal collapsing functions.
The Church–Kleene ordinal and variant ...
at the cost of extra technical difficulty). Throughout the course of this article, \mathsf represents Kripke–Platek set theory
The Kripke–Platek set theory (KP), pronounced , is an axiomatic set theory developed by Saul Kripke and Richard Platek.
The theory can be thought of as roughly the predicative part of ZFC and is considerably weaker than it.
Axioms
In its fo ...
for a \mathsf-reflecting universe, \mathbb_N is the smallest \mathsf-reflecting ordinal, N is a natural number > 2, and \Omega_0 = 0.
Suppose \mathsf for a \mathsf (\Omega)-sentence \mathsf. Then, there exists
In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by the logical operator symbol ∃, which, wh ...
a finite n such that for \alpha = \psi_\Omega(\Omega_n(\mathbb_N + 1)), L_\alpha \models \theta. It can also be proven that \mathsf proves that each initial segment \; n = 1, 2, \ldots is well-founded
In mathematics, a binary relation ''R'' is called well-founded (or wellfounded) on a class ''X'' if every non-empty subset ''S'' ⊆ ''X'' has a minimal element with respect to ''R'', that is, an element ''m'' not related by ''s ...
, and therefore, the proof-theoretic ordinal
In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength.
If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory has ...
of \psi_\Omega(\varepsilon_) is the proof-theoretic ordinal of \mathsf. Using this, \psi_\Omega(\varepsilon_) = \min(\). One can then make the following conversions:
* \psi_\Omega(A) = \psi_0(\Omega) = , \mathsf, = \varphi(1, 0), where A is the least admissible ordinal, \mathsf is Peano arithmetic
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...
and \varphi is the Veblen hierarchy
In mathematics, the Veblen functions are a hierarchy of normal functions (continuous strictly increasing functions from ordinals to ordinals), introduced by Oswald Veblen in . If φ0 is any normal function, then for any non-zero ordinal α, φα ...
.
* \psi_\Omega(\varepsilon_) = \psi_0(\varepsilon_) = , \mathsf, = \mathsf, where A is the least admissible ordinal, \mathsf is Kripke–Platek set theory
The Kripke–Platek set theory (KP), pronounced , is an axiomatic set theory developed by Saul Kripke and Richard Platek.
The theory can be thought of as roughly the predicative part of ZFC and is considerably weaker than it.
Axioms
In its fo ...
and \mathsf is the Bachmann–Howard ordinal
In mathematics, the Bachmann–Howard ordinal (also known as the Howard ordinal, or Howard-Bachmann ordinal) is a large countable ordinal.
It is the proof-theoretic ordinal of several mathematical theories, such as Kripke–Platek set theory (w ...
.
* \psi_\Omega(I) = \psi_0(\Omega_\omega) = , \mathsf, = \mathsf, where I is the least recursively inaccessible ordinal and \mathsf is Buchholz's ordinal In mathematics, ψ0(Ωω), widely known as Buchholz's ordinal, is a large countable ordinal that is used to measure the proof-theoretic strength of some mathematical systems. In particular, it is the proof theoretic ordinal of the subsystem \Pi_1^1- ...
.
* \psi_\Omega(\varepsilon_) = \psi_0(\varepsilon_) = , \mathsf, = \mathsf, where I is the least recursively inaccessible ordinal, \mathsf is Kripke–Platek set theory with a recursively inaccessible universe and \mathsf is the Takeuti–Feferman–Buchholz ordinal In the mathematical fields of set theory and proof theory, the Takeuti–Feferman–Buchholz ordinal (TFBO) is a large countable ordinal, which acts as the limit of the range of Buchholz's psi function and Feferman's theta function. It was named b ...
.
Bachmann's ''ψ''
The first true OCF, Bachmann's \psi 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 \Omega represent an uncountable ordinal such as \omega_1;
* Then define C^(\alpha, \beta) as the closure of \beta \cup \ under addition, (\xi \rightarrow \omega^\xi) and (\xi \rightarrow \psi_\Omega(\xi)) for \xi < \alpha.
* \psi_\Omega(\alpha) is the smallest countable ordinal ρ such that C^\Omega(\alpha, \rho) \cap \Omega= \rho
\psi_\Omega(\varepsilon_) is the Bachmann–Howard ordinal, the proof-theoretic ordinal of Kripke–Platek set theory with the axiom of infinity (KP).
Buchholz's ''ψ''
Buchholz's \psi is a hierarchy of single-argument functions \psi_\nu: \mathsf \rightarrow \mathsf, with \psi_\nu(\alpha) occasionally abbreviated as \psi_\nu\alpha. This function is likely the most well known out of all OCFs. The definition is so:
* Define \Omega_0 = 1 and \Omega_\nu = \aleph_\nu for \nu > 0.
* Let P(\alpha) be the set of distinct terms in the Cantor normal form of \alpha (with each term of the form \omega^\xi for \xi \in \mathsf, see Cantor normal form theorem
In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an exp ...
)
* C^0_\nu(\alpha) = \Omega_\nu
* C^_\nu(\alpha) = C^_\nu(\alpha) \cup \
* C_\nu(\alpha) = \bigcup\limits_ C^n_\nu(\alpha)
* \psi_\nu(\alpha) = \min(\)
The limit of this system is \psi_0(\varepsilon_), the Takeuti–Feferman–Buchholz ordinal In the mathematical fields of set theory and proof theory, the Takeuti–Feferman–Buchholz ordinal (TFBO) is a large countable ordinal, which acts as the limit of the range of Buchholz's psi function and Feferman's theta function. It was named b ...
.
Extended Buchholz's ''ψ''
This OCF is a sophisticated extension of Buchholz's \psi by mathematician Denis Maksudov. The limit of this system is much greater, equal to \psi_0(\Omega_) where \Omega_ denotes the first omega fixed point, sometimes referred to as Extended Buchholz's ordinal. The function is defined as follows:
* Define \Omega_0 = 1 and \Omega_\nu = \aleph_\nu for \nu > 0.
* C^0_\nu(\alpha) = \
* C^_\nu(\alpha) = \
* C_\nu(\alpha) = \bigcup\limits_ C^n_\nu(\alpha)
* \psi_\nu(\alpha) = \min(\)
Madore's ''ψ''
This OCF 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.
* C_0(\alpha) = \
* C_(\alpha) = \
* C(\alpha) = \bigcup\limits_ C_n(\alpha)
* \psi(\alpha) = \min(\)
This function was used by Chris Bird, who also invented the next OCF.
Bird's θ
Chris Bird devised the following shorthand for the extended Veblen function \varphi:
* \theta(\Omega^a_ + \cdots + \Omega^2a_2 + \Omega a_1 + a_0, b) = \varphi(a_, \ldots , a_2, a_1, a_0, b)
* \theta(\alpha, 0) is abbreviated \theta(\alpha)
This function is only defined for arguments less than \Omega^\omega, 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''0 introduced by German mathematician Gerhard Jäger in 1984. It was developed on the base of Buchholz's approach.
* If \kappa = I_\alpha(0) for some ''α'' < ''κ'', \kappa^ = 0.
* If \kappa = I_\alpha(\beta + 1) for some ''α'', ''β'' < ''κ'', \kappa^ = I_\alpha(\beta).
* C^0_\kappa(\alpha) = \ \cup \kappa^
* For every finite ''n'', C^_\kappa(\alpha) \subset M_0 is the smallest set satisfying the following:
** The sum of any finitely many ordinals in C^n_\kappa(\alpha) \subset M_0 belongs to C^_\kappa(\alpha) \subset M_0.
** For any \beta, \gamma \in C^_\kappa(\alpha), \varphi_\beta(\gamma) \in C^_\kappa(\alpha).
** For any \beta, \gamma \in C^_\kappa(\alpha), I_\beta(\gamma) \in C^_\kappa(\alpha).
** For any ordinal γ and uncountable regular cardinal \pi \in C^n_\kappa(\alpha), \gamma < \pi < \kappa \Rightarrow \gamma \in C^_\kappa(\alpha).
** For any \gamma \in \alpha \cap C^n_\kappa(\alpha) and uncountable regular cardinal \pi \in C^n_\kappa(\alpha), \gamma \in C_\pi(\gamma) \Rightarrow \psi_\pi(\gamma) \in C^_\kappa(\alpha).
* C_\kappa(\alpha) = \bigcup\limits_ C^n_\kappa(\alpha)
* \psi_\kappa(\alpha) = \min(\)
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''(''α'', ''β'') = sup(\) for limit ''β''. Restrict ''ρ'' and to uncountable regular ordinals of the form ''I''(''α'', 0) or ''I''(''α'', ''β'' + 1). Then,
* C_0(\alpha, \beta) = \beta \cup \
* C_(\alpha, \beta) = \ \cup \ \cup \
* C(\alpha, \beta) = \bigcup\limits_ C_n(\alpha, \beta)
* \psi_\pi(\alpha) = \min(\)
*
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 M^\alpha, C(\alpha, \pi), \Xi(\alpha), and \Psi^\xi_\pi(\alpha) are defined in mutual recursion in the following way:
* M0 = K \cap \mathsf, where Lim denotes the class of limit ordinals.
* For α > 0, Mα is the set \
* C(\alpha, \beta) is the closure of \beta \cup \ under addition, (\xi, \eta) \rightarrow \varphi(\xi, \eta) , \xi \rightarrow \Omega_\xi given ξ < K, \xi \rightarrow \Xi(\xi) given ξ < α, and (\xi, \pi, \delta) \rightarrow \Psi^\xi_\pi(\delta) given \xi \leq \delta < \alpha .
* \Xi(\alpha) = \min(M^\alpha \cup \) .
* For \xi \leq \alpha , \Psi^\xi_\pi(\alpha) = \min(\ \cup \) .
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
In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength.
If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory ha ...
, 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
In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. More precisely, a cardinal is strongly inaccessible if it is uncountable, it is not a sum o ...
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[ to \Delta^1_2-comprehension plus ]bar induction Bar induction is a reasoning principle used in intuitionistic mathematics, introduced by L. E. J. Brouwer. Bar induction's main use is the intuitionistic derivation of the fan theorem, a key result used in the derivation of the uniform continuity ...
. Roughly speaking, this collapse can be obtained by adding the \alpha \mapsto \Omega_\alpha function itself to the list of constructions to which the C(\cdot) collapsing system applies.
* Michael Rathjen then described the collapse of a Mahlo cardinal In mathematics, a Mahlo cardinal is a certain kind of large cardinal number. Mahlo cardinals were first described by . As with all large cardinals, none of these varieties of Mahlo cardinals can be proven to exist by ZFC (assuming ZFC is consis ...
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 In mathematics, a weakly compact cardinal is a certain kind of cardinal number introduced by ; weakly compact cardinals are large cardinals, meaning that their existence cannot be proven from the standard axioms of set theory. (Tarski originally ...
to describe the ordinal-theoretic strength of Kripke–Platek set theory augmented by certain reflection principle
In set theory, a branch of mathematics, a reflection principle says that it is possible to find sets that resemble the class of all sets. There are several different forms of the reflection principle depending on exactly what is meant by "resemb ...
s (concentrating on the case of \Pi_3-reflection). Very roughly speaking, this proceeds by introducing the first cardinal \Xi(\alpha) which is \alpha-hyper-Mahlo and adding the \alpha \mapsto \Xi(\alpha) function itself to the collapsing system.
* In a 2015 paper, Toshyasu Arai has created ordinal collapsing functions \psi^_\pi for a vector of ordinals \xi, which collapse \Pi_n^1- indescribable cardinals for n>0. These are used to carry out ordinal analysis
In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength.
If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory ha ...
of Kripke–Platek set theory augmented by \Pi_-reflection principles.
* Rathjen has begun[Rathjen, 2005 (Arch. Math. Logic)] the investigation of the collapse of yet larger cardinals, with the ultimate goal of achieving an ordinal analysis of \Pi^1_2-comprehension (which is proof-theoretically equivalent to the augmentation of Kripke–Platek by \Sigma_1-separation).
Notes
References
*
*
*
*
*
*
*
*
*
* (slides of a talk given at Fischbachau)
{{countable ordinals
Ordinal numbers