Content deleted Content added
→References: invoke template of special large countable ordinals |
Rescuing 2 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
| (136 intermediate revisions by 52 users not shown) | |||
Line 1:
{{Short description|Set-theoretic function}}
{{No citations|date=June 2022}}
In [[mathematical logic]] and [[set theory]], an '''ordinal collapsing function''' (or '''projection function''') is a technique for defining ([[Ordinal notation|notations]] for) certain [[Recursive ordinal|recursive]] [[large countable ordinal]]s, whose principle is to give names to certain ordinals much larger than the one being defined, perhaps even [[Large cardinal property|large cardinals]] (though they can be replaced with [[Large countable ordinal#Beyond admissible ordinals|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 [[Impredicativity|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
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 system]]s, typically<ref name="Rathjen-survey">Rathjen, 1995 (Bull. Symbolic Logic)</ref><ref name="Kahle">Kahle, 2002 (Synthese)</ref> subsystems of [[second-order arithmetic|analysis]] (such as those seen in the light of [[reverse mathematics]]), extensions of [[
Ordinal collapsing functions are typically denoted using some variation of either the Greek letter <math>\psi</math> ([[Psi (letter)|psi]]) or <math>\theta</math> ([[theta]]).
== An example leading up to the
The choice of the ordinal collapsing function given as example below imitates greatly the system introduced by Buchholz<ref name="Buchholz">Buchholz, 1986 (Ann. Pure Appl. Logic)</ref> 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 [[#Going beyond the
=== Definition ===
Let <math>\Omega</math> stand for the [[first uncountable ordinal]] <math>\omega_1</math>, or, in fact, any ordinal which is
We define a function <math>\psi</math> (which will be [[Monotonic function|non-decreasing]] and [[Continuous function|continuous]]), taking an arbitrary ordinal <math>\alpha</math> to a countable ordinal <math>\psi(\alpha)</math>, recursively on <math>\alpha</math>, as follows:
Line 24 ⟶ 26:
:<math>\psi(\alpha)</math> is the smallest ordinal which cannot be expressed from <math>0</math>, <math>1</math>, <math>\omega</math> and <math>\Omega</math> using sums, products, exponentials, and the <math>\psi</math> function itself (to previously constructed ordinals less than <math>\alpha</math>).
Here is an attempt to explain the motivation for the definition of <math>\psi</math> 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 [[Cantor's diagonal argument|diagonal schemes]], we seek them in the ordinals far beyond the ones we are constructing (beyond <math>\Omega</math>, that is); so we give names to uncountable ordinals and, since in the end the list of names is necessarily countable, <math>\psi</math> will
=== Computation of values of
To clarify how the function <math>\psi</math> is able to produce notations for certain ordinals, we now compute its first values.
==== Predicative start ====
First consider <math>C(0)</math>. It contains ordinals <math>0
Similarly, <math>C(1)</math> contains the ordinals which can be formed from <math>0</math>, <math>1</math>, <math>\omega</math>, <math>\Omega</math> and this time also <math>\varepsilon_0</math>, using addition, multiplication and exponentiation. This contains all the ordinals up to <math>\varepsilon_1</math> but not the latter, so <math>\psi(1) = \varepsilon_1</math>. In this manner, we prove that <math>\psi(\alpha) = \varepsilon_\alpha</math> inductively on <math>\alpha</math>: the proof works, however, only as long as <math>\alpha<\varepsilon_\alpha</math>. We therefore have:
:<math>\psi(\alpha) = \varepsilon_\alpha = \
(Here, the <math>\
Now <math>\psi(\zeta_0) = \zeta_0</math> but <math>\psi(\zeta_0+1)</math> is no larger, since <math>\zeta_0</math> cannot be constructed using finite applications of <math>\
:<math>\psi(\alpha) = \zeta_0</math> for all <math>\zeta_0 \leq \alpha \leq \Omega</math>.
==== First impredicative values ====
Again, <math>\psi(\Omega) = \zeta_0</math>. However, when we come to computing <math>\psi(\Omega+1)</math>, something has changed: since <math>\Omega</math> was (
We say that the definition <math>\psi(\Omega) = \zeta_0</math> and the next values of the function <math>\psi</math> such as <math>\psi(\Omega+1) = \varepsilon_{\zeta_0+1}</math> are [[Impredicativity|impredicative]] because they use ordinals (here, <math>\Omega</math>) greater than the ones which are being defined (here, <math>\zeta_0</math>).
==== Values of
The fact that <math>\psi(\Omega+\alpha)</math>
The same reasoning shows that <math>\psi(\Omega(1+\alpha)) = \
Again, we can see that <math>\psi(\Omega^\alpha) = \
==== Beyond the
We have <math>\psi(\Omega^\Omega+\Omega^\alpha) = \
* <math>\psi(\Omega^{\Omega^2})</math> is the [[Ackermann ordinal]] (the range of the notation <math>\
* <math>\psi(\Omega^{\Omega^\omega})</math> is the [[small Veblen ordinal|
* <math>\psi(\Omega^{\Omega^\Omega})</math> is the [[large Veblen ordinal|
* the limit <math>\psi(\varepsilon_{\Omega+1})</math> of <math>\psi(\Omega)</math>, <math>\psi(\Omega^\Omega)</math>, <math>\psi(\Omega^{\Omega^\Omega})</math>, etc., is the [[
=== Ordinal notations up to the
We now explain more systematically how the <math>\psi</math> function defines notations for ordinals up to the
==== A note about base representations ====
Recall that if <math>\delta</math> is an ordinal which is a power of <math>\omega</math> (for example <math>\omega</math> itself, or <math>\varepsilon_0</math>, or <math>\Omega</math>), any ordinal <math>\alpha</math> can be uniquely expressed in the form <math>\delta^{\beta_1}\gamma_1 + \ldots + \delta^{\beta_k}\gamma_k</math>, where <math>k</math> is a [[natural number]], <math>\gamma_1,\ldots,\gamma_k</math> are non-zero ordinals less than <math>\delta</math>, and <math>\beta_1 > \beta_2 > \cdots > \beta_k</math> are ordinal numbers (we allow <math>\beta_k=0</math>). This
If <math>\alpha</math> is an ordinal less than <math>\varepsilon_{\Omega+1}</math>, then its base <math>\Omega</math> representation has coefficients <math>\gamma_i<\Omega</math> (by definition) and exponents <math>\beta_i<\alpha</math> (because of the assumption <math>\alpha < \varepsilon_{\Omega+1}</math>): hence one can rewrite these exponents in base <math>\Omega</math> and repeat the operation until the process terminates (any decreasing sequence of ordinals is finite). We call the resulting expression the ''iterated base <math>\Omega</math> representation'' of <math>\alpha</math> and the various coefficients involved (including as exponents) the ''pieces'' of the representation (they are all <math><\Omega</math>), or, for short, the <math>\Omega</math>-pieces of <math>\alpha</math>.
==== Some properties of
* The function <math>\psi</math> is non-decreasing and continuous (this is more or less obvious from its definition).
* If <math>\psi(\alpha) = \psi(\beta)</math> with <math>\beta<\alpha</math> then necessarily <math>C(\alpha) = C(\beta)</math>. Indeed, no ordinal <math>\beta'</math> with <math>\beta\leq\beta'<\alpha</math> can belong to <math>C(\alpha)</math> (otherwise its image by <math>\psi</math>, which is <math>\psi(\alpha)</math> would belong to <math>C(\alpha)</math> — impossible); so <math>C(\beta)</math> is closed by everything under which <math>C(\alpha)</math> is the closure, so they are equal.
Line 79 ⟶ 81:
==== The ordinal notation ====
Using the facts above, we can define a (canonical) ordinal notation for every <math>\gamma</math> less than the
If <math>\gamma</math> is less than <math>\varepsilon_0</math>, we use the iterated Cantor normal form of <math>\gamma</math>. Otherwise, there exists a largest <math>\varepsilon</math>-number <math>\delta</math> less or equal to <math>\gamma</math> (this is because the set of <math>\varepsilon</math>-numbers is closed): if <math>\delta<\gamma</math> then by induction we have defined a notation for <math>\delta</math> and the base <math>\delta</math> representation of <math>\gamma</math> gives one for <math>\gamma</math>, so we are finished.
Line 85 ⟶ 87:
It remains to deal with the case where <math>\gamma=\delta</math> is an <math>\varepsilon</math>-number: we have argued that, in this case, we can write <math>\delta = \psi(\alpha)</math> for some (possibly uncountable) ordinal <math>\alpha<\varepsilon_{\Omega+1}</math>: let <math>\alpha</math> be the ''greatest'' possible such ordinal (which exists since <math>\psi</math> is continuous). We use the iterated base <math>\Omega</math> representation of <math>\alpha</math>: it remains to show that every piece of this representation is less than <math>\delta</math> (so we have already defined a notation for it). If this is ''not'' the case then, by the properties we have shown, <math>C(\alpha)</math> does not contain <math>\alpha</math>; but then <math>C(\alpha+1)=C(\alpha)</math> (they are closed under the same operations, since the value of <math>\psi</math> at <math>\alpha</math> can never be taken), so <math>\psi(\alpha+1)=\psi(\alpha)=\delta</math>, contradicting the maximality of <math>\alpha</math>.
'''Note''': Actually, we have defined canonical notations not just for ordinals below the
==== Examples ====
Line 94 ⟶ 96:
Beyond this, we may need to express ordinals beyond <math>\Omega</math>: this is always done in iterated <math>\Omega</math>-base, and the pieces themselves need to be expressed using the largest possible <math>\varepsilon</math>-number base which gives a non-trivial representation.
Note that while <math>\psi(\varepsilon_{\Omega+1})</math> is equal to the
==== Conditions for canonicalness ====
The notations thus defined have the property that whenever they nest <math>\psi</math> functions, the arguments of the
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 <math>\varepsilon_0</math>, or an iterated base <math>\delta</math> representation all of whose pieces are canonical, for some <math>\delta=\psi(\alpha)</math> where <math>\alpha</math> is itself written in iterated base <math>\Omega</math> representation all of whose pieces are canonical and less than <math>\delta</math>. The order is checked by lexicographic verification at all levels (keeping in mind that <math>\Omega</math> is greater than any expression obtained by <math>\psi</math>, and for canonical values the greater <math>\psi</math> always trumps the lesser or even arbitrary sums, products and exponentials of the lesser).
For example, <math>\psi(\Omega^{\omega+1}\,\psi(\Omega) + \psi(\Omega^\omega)^{\psi(\Omega^2)}42)^{\psi(1729)\,\omega}</math> is a canonical notation for an ordinal which is less than the
Concerning the order, one might point out that <math>\psi(\Omega^\Omega)</math> (the
=== Standard sequences for ordinal notations ===
{{main|Fundamental sequence (ordinals)}}
To witness the fact that we have defined notations for ordinals below the
The following rules are more or less obvious, except for the last:
Line 116 ⟶ 118:
** if <math>\gamma_k</math> is successor and <math>\beta_k</math> is limit, rewrite the last term <math>\delta^{\beta_k}\gamma_k</math> as <math>\delta^{\beta_k}(\gamma_k-1) + \delta^{\beta_k}</math> and replace the exponent <math>\beta_k</math> in the last term by the elements of the fundamental sequence converging to it;
** if <math>\gamma_k</math> is successor and <math>\beta_k</math> is also, rewrite the last term <math>\delta^{\beta_k}\gamma_k</math> as <math>\delta^{\beta_k}(\gamma_k-1) + \delta^{\beta_k-1}\delta</math> and replace the last <math>\delta</math> in this expression by the elements of the fundamental sequence converging to it.
* If <math>\delta</math> is <math>\omega</math>, then take the obvious <math>0
* If <math>\delta = \psi(0)</math> then take as fundamental sequence for <math>\delta</math> the sequence <math>\omega
* If <math>\delta = \psi(\alpha+1)</math> then take as fundamental sequence for <math>\delta</math> the sequence <math>\psi(\alpha)
* If <math>\delta = \psi(\alpha)</math> where <math>\alpha</math> is a limit ordinal of ''countable'' cofinality, define the standard sequence for <math>\delta</math> to be obtained by applying <math>\psi</math> to the standard sequence for <math>\alpha</math> (recall that <math>\psi</math> is continuous and increasing, here).
* It remains to handle the case where <math>\delta = \psi(\alpha)</math> with <math>\alpha</math> an ordinal of ''uncountable'' cofinality (e.g., <math>\Omega</math> itself). Obviously it doesn't make sense to define a sequence converging to <math>\alpha</math> in this case; however, what we can define is a sequence converging to some <math>\rho<\alpha</math> with countable cofinality and such that <math>\psi</math> is constant between <math>\rho</math> and <math>\alpha</math>. This <math>\rho</math> will be the first fixed point of a certain (continuous and non-decreasing) function <math>\xi\mapsto h(\psi(\xi))</math>. To find it, apply the same rules (from the base <math>\Omega</math> representation of <math>\alpha</math>) as to find the canonical sequence of <math>\alpha</math>, except that whenever a sequence converging to <math>\Omega</math> is called for (something which cannot exist), replace the <math>\Omega</math> in question, in the expression of <math>\alpha = h(\Omega)</math>, by a <math>\psi(\xi)</math> (where <math>\xi</math> is a variable) and perform a repeated iteration (starting from <math>0</math>, say) of the function <math>\xi\mapsto h(\psi(\xi))</math>: this gives a sequence <math>0
Here are some examples for the last (and most interesting) case:
* The canonical sequence for <math>\psi(\Omega)</math> is: <math>\psi(0)</math>, <math>\psi(\psi(0))</math>, <math>\psi(\psi(\psi(0)))</math>
* The canonical sequence for <math>\psi(\Omega 2)</math> is: <math>\psi(0)</math>, <math>\psi(\Omega+\psi(0))</math>, <math>\psi(\Omega+\psi(\Omega+\psi(0))),\ldots</math>
* The canonical sequence for <math>\psi(\Omega^2)</math> is: <math>\psi(0)
* The canonical sequence for <math>\psi(\Omega^2 3 + \Omega)</math> is <math>\psi(0)
* The canonical sequence for <math>\psi(\Omega^\Omega)</math> is: <math>\psi(0)
* The canonical sequence for <math>\psi(\Omega^\Omega 3)</math> is: <math>\psi(0)
* The canonical sequence for <math>\psi(\Omega^{\Omega+1})</math> is: <math>\psi(0)
* The canonical sequence for <math>\psi(\Omega^{\Omega^2+\Omega 3})</math> is: <math>\psi(0)
Here are some examples of the other cases:
* The canonical sequence for <math>\omega^2</math> is: <math>0</math>, <math>\omega</math>, <math>\omega 2</math>, <math>\omega 3</math>
* The canonical sequence for <math>\psi(\omega^\omega)</math> is: <math>\psi(1)</math>, <math>\psi(\omega)</math>, <math>\psi(\omega^2)</math>, <math>\psi(\omega^3)</math>
* The canonical sequence for <math>\psi(\Omega)^\omega</math> is: <math>1</math>, <math>\psi(\Omega)</math>, <math>\psi(\Omega)^2</math>, <math>\psi(\Omega)^3</math>
* The canonical sequence for <math>\psi(\Omega+1)</math> is: <math>\psi(\Omega)</math>, <math>\psi(\Omega)^{\psi(\Omega)}</math>, <math>\psi(\Omega)^{\psi(\Omega)^{\psi(\Omega)}}</math>
* The canonical sequence for <math>\psi(\Omega+\omega)</math> is: <math>\psi(\Omega)</math>, <math>\psi(\Omega+1)</math>, <math>\psi(\Omega+2)</math>, <math>\psi(\Omega+3)</math>
* The canonical sequence for <math>\psi(\Omega\omega)</math> is: <math>\psi(0)</math>, <math>\psi(\Omega)</math>, <math>\psi(\Omega 2)</math>, <math>\psi(\Omega 3)</math>
* The canonical sequence for <math>\psi(\Omega^\omega)</math> is: <math>\psi(1)</math>, <math>\psi(\Omega)</math>, <math>\psi(\Omega^2)</math>, <math>\psi(\Omega^3)</math>
* The canonical sequence for <math>\psi(\Omega^{\psi(0)})</math> is: <math>\psi(\Omega^\omega)</math>, <math>\psi(\Omega^{\omega^\omega})</math>, <math>\psi(\Omega^{\omega^{\omega^\omega}})</math>
* The canonical sequence for <math>\psi(\Omega^{\psi(\Omega)})</math> is: <math>\psi(\Omega^{\psi(0)})</math>, <math>\psi(\Omega^{\psi(\psi(0))})</math>, <math>\psi(\Omega^{\psi(\psi(\psi(0)))})</math>
Even though the
=== A terminating process ===
Start with any ordinal less than or equal to the
* 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.
Line 153 ⟶ 155:
# 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 <math>\psi(\Omega^{\Omega^\omega})</math> (the small Veblen ordinal), we might go down to <math>\psi(\Omega^{\Omega^3})</math>, from there down to <math>\psi(\Omega^{\Omega^2 \psi(0)})</math>, then <math>\psi(\Omega^{\Omega^2 \omega^\omega})</math> then <math>\psi(\Omega^{\Omega^2 \omega^3})</math> then <math>\psi(\Omega^{\Omega^2 \omega^2
Concerning the first statement, one could introduce, for any ordinal <math>\alpha</math> less or equal to the
Concerning the second statement, a precise version is given by [[ordinal analysis]]: for example, [[
== Variations on the example ==
Line 164 ⟶ 166:
It is instructive (although not exactly useful) to make <math>\psi</math> less powerful.
If we alter the definition of <math>\psi</math> above to omit exponentiation from the repertoire from which <math>C(\alpha)</math> is constructed, then we get <math>\psi(0) = \omega^\omega</math> (as this is the smallest ordinal which cannot be constructed from <math>0</math>, <math>1</math> and <math>\omega</math> using addition and multiplication only), then <math>\psi(1) = \omega^{\omega^2}</math> and similarly <math>\psi(\omega) = \omega^{\omega^\omega}</math>, <math>\psi(\psi(0)) = \omega^{\omega^{\omega^\omega}}</math> until we come to a fixed point which is then our <math>\psi(\Omega) = \varepsilon_0</math>. We then have <math>\psi(\Omega+1) = {\varepsilon_0}^\omega</math> and so on until <math>\psi(\Omega 2) = \varepsilon_1</math>. Since multiplication of <math>\Omega</math>'s is permitted, we can still form <math>\psi(\Omega^2) = \
If we alter the definition of <math>\psi</math> yet some more to allow only addition as a primitive for construction, we get <math>\psi(0) = \omega^2</math> and <math>\psi(1) = \omega^3</math> and so on until <math>\psi(\psi(0)) = \omega^{\omega^2}</math> and still <math>\psi(\Omega) = \varepsilon_0</math>. This time, <math>\psi(\Omega+1) = \varepsilon_0 \omega</math> and so on until <math>\psi(\Omega 2) = \varepsilon_1</math> and similarly <math>\psi(\Omega 3) = \varepsilon_2</math>. But this time we can go no further: since we can only add <math>\Omega</math>'s, the range of our system is <math>\psi(\Omega\omega) = \varepsilon_\omega = \
If we alter the definition even more, to allow nothing except psi, we get <math>\psi(0) = 1</math>, <math>\psi(\psi(0)) = 2</math>, and so on until <math>\psi(\omega) = \omega+1</math>, <math>\psi(\psi(\omega)) = \omega+2</math>, and <math>\psi(\Omega) = \omega 2</math>, at which point we can go no further since we cannot do anything with the <math>\Omega</math>'s. So the range of this system is only <math>\omega 2</math>.
In both cases, we find that the limitation on the weakened <math>\psi</math> 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
We know that <math>\psi(\varepsilon_{\Omega+1})</math> is the
:Let <math>\psi_1(\alpha)</math> be the smallest ordinal which cannot be expressed from all countable ordinals
Here, <math>\Omega_2</math> is a new ordinal guaranteed to be greater than all the ordinals which will be constructed using <math>\psi_1</math>: again, letting <math>\Omega = \omega_1</math> and <math>\Omega_2 = \omega_2</math> works.
For example, <math>\psi_1(0) =
The <math>\psi_1</math> function gives us a system of notations (''assuming'' we can somehow write down all countable ordinals!) for the uncountable ordinals below <math>\psi_1(\varepsilon_{\Omega_2+1})</math>, which is the limit of <math>\psi_1(\Omega_2)</math>, <math>\psi_1({\Omega_2}^{\Omega_2})</math> and so forth.
Line 184 ⟶ 188:
:<math>\psi(\alpha)</math> is the smallest ordinal which cannot be expressed from <math>0</math>, <math>1</math>, <math>\omega</math>, <math>\Omega</math> and <math>\Omega_2</math> using sums, products, exponentials, the <math>\psi_1</math> function, and the <math>\psi</math> function itself (to previously constructed ordinals less than <math>\alpha</math>).
This modified function <math>\psi</math> coincides with the previous one up to (and including) <math>\psi(\psi_1(
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
:<math>\psi(\alpha)</math> is the smallest ordinal which cannot be expressed from <math>0</math>, <math>1</math>, <math>\omega</math>, <math>\Omega</math> and <math>\Omega_2</math> using sums, products, exponentials, and the <math>\psi_1</math> and <math>\psi</math> function (to previously constructed ordinals less than <math>\alpha</math>).
i.e., allow the use of <math>\psi_1</math> only for arguments less than <math>\alpha</math> itself. With this definition, we must write <math>\psi(\Omega_2)</math> instead of <math>\psi(\psi_1(\Omega_2))</math> (although it is still also equal to <math>\psi(\psi_1(\Omega_2)) = \psi(\zeta_{\Omega+1})</math>, of course, but it is now constant until <math>\Omega_2</math>). This change is inessential because, intuitively speaking, the <math>\psi_1</math> function collapses the nameable ordinals beyond <math>\Omega_2</math> below the latter so it matters little whether <math>\psi</math> is invoked directly on the ordinals beyond <math>\Omega_2</math> or on their image by <math>\psi_1</math>. But it makes it possible to define <math>\psi</math> and <math>\psi_1</math> by ''simultaneous'' (rather than
Indeed, there is no reason to stop at two levels: using <math>\omega+1</math> new cardinals in this way, <math>\Omega_1,\Omega_2,\ldots,\Omega_\omega</math>, we get a system essentially equivalent to that introduced by Buchholz,<ref name="Buchholz"/> the inessential difference being that since Buchholz uses <math>\omega+1</math> ordinals from the start, he does not need to allow multiplication or exponentiation; also, Buchholz does not introduce the numbers <math>1</math> or <math>\omega</math> in the system as they will also be produced by the <math>\psi</math> 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)
<!-- You can also have <math>\Omega</math> or more cardinals, in fact as many as nesting of the ψ function allows:
:<math>\psi_\nu(\alpha)</math> is the smallest ordinal which cannot be expressed from <math>0</math>, <math>1</math>, <math>\omega</math>, and all ordinals smaller than <math>\Omega_\nu</math> using sums, products, exponentials, and the <math>\psi_\kappa</math> functions (for <math>\kappa</math> being a previously constructed ordinal) to previously constructed ordinals less than <math>\alpha</math>.
<math>\Omega_0</math> being 0 here, abbreviate <math>\psi_0</math> as <math>\psi</math>. The limit of this system is <math>\psi(\text{The first ordinal }\alpha\text{ such that }\Omega_\alpha = \alpha)</math>. -->
=== A "normal" variant ===
Line 205 ⟶ 214:
:Let <math>\tilde C(\alpha,\beta)</math> be the set of ordinals generated starting from <math>0</math>, <math>1</math>, <math>\omega</math>, <math>\Omega</math> and all ordinals less than <math>\beta</math> by recursively applying the following functions: ordinal addition, multiplication and exponentiation, and the function <math>\tilde\psi\upharpoonright_\alpha</math>. Then <math>\tilde\psi(\alpha)</math> is defined as the smallest ordinal <math>\rho</math> such that <math>\tilde C(\alpha,\rho) \cap \Omega = \rho</math> and <math>\alpha \in \tilde C(\alpha,\rho)</math>.
The first values of <math>\tilde\psi</math> coincide with those of <math>\psi</math>: namely, for all <math>\alpha<\zeta_0</math> where <math>\zeta_0 = \varphi_2(0)</math>, we have <math>\tilde\psi(\alpha) = \psi(\alpha)</math> because the additional clause <math>\alpha \in \tilde C(\alpha,\rho)</math> is always satisfied. But at this point the functions start to differ: while the function <math>\psi</math> gets
Despite these changes, the <math>\tilde\psi</math> 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, <math>\psi(\Omega+1+\alpha) = \tilde\psi(\tilde\psi(\Omega)+\alpha)</math> for all <math>\alpha</math> less than the common value <math>\psi(\Omega2) = \tilde\psi(\Omega+1)</math>).
== Other similar OCFs ==
=== 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''. <math>\psi_\Omega(\alpha)</math> is a collapsing function such that <math>\psi_\Omega(\alpha) < \Omega</math>, where <math>\Omega</math> represents the [[first uncountable ordinal]] (it can be replaced by the [[Nonrecursive ordinal|Church–Kleene ordinal]] at the cost of extra technical difficulty). Throughout the course of this article, <math>\mathsf{KP\Pi_N}</math> represents [[Kripke–Platek set theory]] for a <math>\mathsf{\Pi_N}</math>-reflecting universe, <math>\mathbb{K}_N</math> is the least <math>\mathsf{\Pi}^1_{N-2}</math>-indescribable cardinal (it may be replaced with the least <math>\mathsf{\Pi}_N</math>-reflecting ordinal at the cost of extra technical difficulty), <math>N</math> is a fixed natural number <math>\ge 3</math>, and <math>\Omega_0 = 0</math>.
Suppose <math>\mathsf{KP\Pi_N} \vdash \theta</math> for a <math>\mathsf{\Sigma_1}</math> (<math>\Omega</math>)-sentence <math>\mathsf{\theta}</math>. Then, [[Existential quantification|there exists]] a finite <math>n</math> such that for <math>\alpha = \psi_\Omega(\omega_n(\mathbb{K}_N + 1))</math>, <math>L_\alpha \models \theta</math>. It can also be proven that <math>\mathsf{KP\Pi_N}</math> proves that each initial segment <math>\{\alpha \in OT: \alpha < \psi_\Omega(\omega_n(\mathbb{K}_N + 1))\}; n = 1, 2, \ldots</math> is [[Well-founded relation|well-founded]], and therefore, <math>\psi_\Omega(\varepsilon_{\mathbb{K}_N+1})</math> is the [[Ordinal analysis|proof-theoretic ordinal]] of <math>\mathsf{KP\Pi_N}</math>. One can then make the following conversions:
* <math>\psi_{\Omega}(\varepsilon_{\Omega + 1}) = |\mathsf{KP\omega}| = \mathsf{BHO}</math>, where <math>\Omega</math> is either the least recursively regular ordinal or the least uncountable cardinal, <math>\mathsf{KP\omega}</math> is [[Kripke–Platek set theory]] with infinity and <math>\mathsf{BHO}</math> is the [[Bachmann–Howard ordinal]].
* <math>\psi_{\Omega}(\Omega_{\omega}) = |\mathsf{\Pi^1_1-CA_0}| = \mathsf{BO}</math>, where <math>\Omega_{\omega}</math> is either the least limit of admissible ordinals or the least limit of infinite cardinals and <math>\mathsf{BO}</math> is [[Buchholz's ordinal]].
* <math>\psi_{\Omega}(\varepsilon_{\Omega_{\omega} + 1}) = |\mathsf{KPl}| = \mathsf{TFBO}</math>, where <math>\Omega_{\omega}</math> is either the least limit of admissible ordinals or the least limit of infinite cardinals, <math>\mathsf{KPl}</math> is KPi without the collection scheme and <math>\mathsf{TFBO}</math> is the [[Takeuti–Feferman–Buchholz ordinal]].
* <math>\psi_{\Omega}(\varepsilon_{I + 1}) = |\mathsf{KPi}|</math>, where <math>I</math> is either the least recursively inaccessible ordinal or the least weakly inaccessible cardinal and <math>\mathsf{KPi}</math> is Kripke–Platek set theory with a recursively inaccessible universe.
=== Bachmann's ''ψ'' ===
The first true OCF, Bachmann's <math>\psi</math> 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 <math>\Omega</math> represent an uncountable ordinal such as <math>\omega_1</math>;
* Then define <math>C^{\Omega}(\alpha, \beta)</math> as the closure of <math>\beta \cup \{ 0, \Omega\}</math> under addition, <math>(\xi \rightarrow \omega^\xi)</math> and <math>(\xi \rightarrow \psi_\Omega(\xi))</math> for <math>\xi < \alpha</math>.
* <math>\psi_\Omega(\alpha)</math> is the smallest countable ordinal ρ such that <math>C^\Omega(\alpha, \rho) \cap \Omega= \rho</math>
<math>\psi_\Omega(\varepsilon_{\Omega+1})</math> is the Bachmann–Howard ordinal, the proof-theoretic ordinal of Kripke–Platek set theory with the [[axiom of infinity]] (KP).
=== Buchholz's ''ψ'' ===
{{Main|Buchholz psi functions}}
Buchholz's <math>\psi</math> is a hierarchy of single-argument functions <math>\psi_\nu: \mathsf{On} \rightarrow \mathsf{On}</math>, with <math>\psi_\nu(\alpha)</math> occasionally abbreviated as <math>\psi_\nu\alpha</math>. This function is likely the most well known out of all OCFs. The definition is so:
* Define <math>\Omega_0 = 1</math> and <math>\Omega_\nu = \aleph_\nu</math> for <math>\nu > 0</math>.
* Let <math>P(\alpha)</math> be the set of distinct terms in the Cantor normal form of <math>\alpha</math> (with each term of the form <math>\omega^\xi</math> for <math>\xi \in \mathsf{On}</math>, see [[Cantor normal form theorem]])
* <math>C^0_\nu(\alpha) = \Omega_\nu</math>
* <math>C^{n+1}_\nu(\alpha) = C^{n}_\nu(\alpha) \cup \{\gamma \mid P(\gamma) \subseteq C^{n}_\nu (\alpha) \} \cup \{\psi_\nu(\xi) \mid \xi \in \alpha \cap C^{n}_\nu(\alpha) \land \xi \in C_u(\xi) \land u \leq \omega \}</math>
* <math>C_\nu(\alpha) = \bigcup\limits_{n < \omega} C^n_\nu(\alpha)</math>
* <math>\psi_\nu(\alpha) = \min(\{\gamma \mid \gamma \notin C_\nu(\alpha)\})</math>
The limit of this system is <math>\psi_0(\varepsilon_{\Omega_\omega + 1})</math>, the [[Takeuti–Feferman–Buchholz ordinal]].
=== Extended Buchholz's ''ψ'' ===
{{Main|Buchholz psi functions#Extension}}
This OCF is a sophisticated extension of Buchholz's <math>\psi</math> by mathematician Denis Maksudov. The limit of this system, sometimes called the Extended Buchholz Ordinal, is much greater, equal to <math>\psi_0(\Omega_{\Omega_{\Omega_{\cdots}}})</math> where <math>\Omega_{\Omega_{\Omega_{...}}}</math> denotes the first omega fixed point. The function is defined as follows:
* Define <math>\Omega_0 = 1</math> and <math>\Omega_\nu = \aleph_\nu</math> for <math>\nu > 0</math>.
* <math>C^0_\nu(\alpha) = \{\beta \mid \beta < \Omega_\nu\}</math>
* <math>C^{n+1}_\nu(\alpha) = \{\beta + \gamma, \psi_\mu(\eta) \mid \mu, \beta, \gamma, \eta \in C^{n}_\nu(\alpha) \land \eta < \alpha\}</math>
* <math>C_\nu(\alpha) = \bigcup\limits_{n < \omega} C^n_\nu(\alpha)</math>
* <math>\psi_\nu(\alpha) = \min(\{\gamma \mid \gamma \notin C_\nu(\alpha)\})</math>
=== 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.
* <math>C_0(\alpha) = \{0, 1, \omega, \Omega\}</math>
* <math>C_{n+1}(\alpha) = \{\gamma + \delta, \gamma\delta, \gamma^\delta, \psi(\eta) \mid \gamma, \delta, \eta \in C_n(\alpha); \eta < \alpha\}</math>
* <math>C(\alpha) = \bigcup\limits_{n < \omega} C_n(\alpha)</math>
* <math>\psi(\alpha) = \min(\{\beta \in \Omega \mid \beta \notin C(\alpha)\})</math>
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 <math>\varphi</math>:
* <math>\theta(\Omega^{n-1}a_{n-1} + \cdots + \Omega^2a_2 + \Omega a_1 + a_0, b) = \varphi(a_{n-1}, \ldots , a_2, a_1, a_0, b)</math>
* <math>\theta(\alpha, 0)</math> is abbreviated <math>\theta(\alpha)</math>
This function is only defined for arguments less than <math>\Omega^\omega</math>, and its outputs are limited by the small Veblen ordinal.
=== Jäger's ''ψ'' ===
Jäger's ''ψ'' is a hierarchy of single-argument ordinal functions ''ψ''<sub>''κ''</sub> indexed by uncountable regular cardinals ''κ'' smaller than the least weakly Mahlo cardinal ''M''<sub>0</sub> introduced by German mathematician Gerhard Jäger in 1984. It was developed on the base of Buchholz's approach.
* If <math>\kappa = I_\alpha(0)</math> for some ''α'' < ''κ'', <math>\kappa^{-} = 0</math>.
* If <math>\kappa = I_\alpha(\beta + 1)</math> for some ''α'', ''β'' < ''κ'', <math>\kappa^{-} = I_\alpha(\beta)</math>.
* <math>C^0_\kappa(\alpha) = \{\kappa^{-}\} \cup \kappa^{-}</math>
* For every finite ''n'', <math>C^{n + 1}_\kappa(\alpha) \subset M_0</math> is the smallest set satisfying the following:
** The sum of any finitely many ordinals in <math>C^n_\kappa(\alpha) \subset M_0</math> belongs to <math>C^{n + 1}_\kappa(\alpha) \subset M_0</math>.
** For any <math>\beta, \gamma \in C^{n}_\kappa(\alpha)</math>, <math>\varphi_\beta(\gamma) \in C^{n + 1}_\kappa(\alpha)</math>.
** For any <math>\beta, \gamma \in C^{n}_\kappa(\alpha)</math>, <math>I_\beta(\gamma) \in C^{n + 1}_\kappa(\alpha)</math>.
** For any ordinal γ and uncountable regular cardinal <math>\pi \in C^n_\kappa(\alpha)</math>, <math>\gamma < \pi < \kappa \Rightarrow \gamma \in C^{n + 1}_\kappa(\alpha)</math>.
** For any <math>\gamma \in \alpha \cap C^n_\kappa(\alpha)</math> and uncountable regular cardinal <math>\pi \in C^n_\kappa(\alpha)</math>, <math>\gamma \in C_\pi(\gamma) \Rightarrow \psi_\pi(\gamma) \in C^{n + 1}_\kappa(\alpha)</math>.
* <math>C_\kappa(\alpha) = \bigcup\limits_{n < \omega} C^n_\kappa(\alpha)</math>
* <math>\psi_\kappa(\alpha) = \min(\{\xi \in \kappa \mid \xi \notin C_\kappa(\alpha)\})</math>
=== 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''(''α'', ''β'') = <math>sup(\{I(\alpha, \gamma) \mid \gamma < \beta\})</math> for limit ''β''. Restrict ''ρ'' and {{pi}} to uncountable regular ordinals of the form ''I''(''α'', 0) or ''I''(''α'', ''β'' + 1). Then,
* <math>C_0(\alpha, \beta) = \beta \cup \{0\}</math>
* <math>C_{n + 1}(\alpha, \beta) = \{\gamma + \delta \mid \gamma, \delta \in C_n(\alpha, \beta)\} \cup \{I(\gamma, \delta) \mid \gamma, \delta \in C_n(\alpha, \beta)\} \cup \{\psi_\pi(\gamma) \mid \pi, \gamma, \in C_n(\alpha, \beta) \land \gamma < \alpha\}</math>
* <math>C(\alpha, \beta) = \bigcup\limits_{n < \omega} C_n(\alpha, \beta)</math>
* <math>\psi_\pi(\alpha) = \min(\{\beta < \pi \mid C(\alpha, \beta) \cap \pi \subseteq \beta \})</math>
*
=== Rathjen's ''Ψ'' ===
{{Main|Rathjen's psi function}}
Rathjen's ''Ψ'' function is based on the least weakly compact cardinal to create large countable ordinals. For a weakly compact cardinal K, the functions <math>M^\alpha</math>, <math>C(\alpha, \pi)</math>, <math>\Xi(\alpha)</math>, and <math>\Psi^\xi_\pi(\alpha)</math> are defined in mutual recursion in the following way:
* M<sup>0</sup> = <math>K \cap \mathsf{Lim}</math>, where Lim denotes the class of limit ordinals.
* For α > 0, M<sup>α</sup> is the set <math>\{\pi < K \mid C(\alpha, \pi) \cap K = \pi \land \forall \xi \in C(\alpha, \pi) \cap \alpha, M^\xi \mathsf{} </math> is stationary in <math>\pi \land \alpha \in C(\alpha, \pi)\} </math>
* <math>C(\alpha, \beta) </math> is the closure of <math>\beta \cup \{0, K\} </math> under addition, <math>(\xi, \eta) \rightarrow \varphi(\xi, \eta) </math>, <math>\xi \rightarrow \Omega_\xi </math> given ξ < K, <math>\xi \rightarrow \Xi(\xi) </math> given ξ < α, and <math>(\xi, \pi, \delta) \rightarrow \Psi^\xi_\pi(\delta) </math> given <math>\xi \leq \delta < \alpha </math>.
* <math>\Xi(\alpha) = \min(M^\alpha \cup \{K\}) </math>.
* For <math>\xi \leq \alpha </math>, <math>\Psi^\xi_\pi(\alpha) = \min(\{\rho \in M^\xi \cap \pi: C(\alpha, \rho) \cap \pi = \rho \land \pi, \alpha \in C(\alpha, \rho)\} \cup \{\pi\}) </math>.
=== 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<ref>Jäger & Pohlers, 1983 (Bayer. Akad. Wiss. Math.-Natur. Kl. Sitzungsber.)</ref> described the collapse of an [[inaccessible cardinal]] to describe the ordinal-theoretic strength of
* Michael Rathjen<ref>Rathjen, 1991 (Arch. Math. Logic)</ref> then described the collapse of a [[Mahlo cardinal]] to describe the ordinal-theoretic strength of
* Rathjen<ref>Rathjen, 1994 (Ann. Pure Appl. Logic)</ref> later described the collapse of a [[weakly compact cardinal]] to describe the ordinal-theoretic strength of
* In a 2015 paper, Toshyasu Arai has created ordinal collapsing functions <math>\psi^{\vec \xi}_\pi</math> for a vector of ordinals <math>\xi</math>, which collapse <math>\Pi_n^1</math>-[[Indescribable cardinal|indescribable cardinals]] for <math>n>0</math>. These are used to carry out [[ordinal analysis]] of Kripke–Platek set theory augmented by <math>\Pi_{n+2}</math>-reflection principles. <ref>T. Arai, [https://arxiv.org/abs/1907.07611v1 A simplified analysis of first-order reflection] (2015).</ref>
* Rathjen has investigated the collapse of yet larger cardinals, with the ultimate goal of achieving an ordinal analysis of <math>\Pi^1_2</math>-comprehension (which is proof-theoretically equivalent to the augmentation of Kripke–Platek by <math>\Sigma_1</math>-separation).<ref>Rathjen, 2005 (Arch. Math. Logic)</ref>
== Notes ==
Line 221 ⟶ 327:
== References ==
* {{cite journal |
* {{cite journal | last=Takeuti | first=Gaisi | authorlink=Gaisi Takeuti | title=Consistency proofs of subsystems of classical analysis | journal=Annals of Mathematics | volume=86 | year=1967 | pages=299–348 | doi=10.2307/1970691 | issue=2 | jstor=1970691 }}
* {{cite journal | last=Jäger | first=Gerhard |author2=Pohlers, Wolfram | title=Eine beweistheoretische Untersuchung von (<math>\Delta^1_2</math>-CA)+(BI) und verwandter Systeme | journal=Bayerische Akademie der Wissenschaften. Mathematisch-Naturwissenschaftliche Klasse Sitzungsberichte | volume=1982 | year=1983 | pages=1–28 }}
* {{cite journal | last=Buchholz | first=Wilfried | title=A New System of Proof-Theoretic Ordinal
* {{cite journal | last=Rathjen | first=Michael | title=Proof-theoretic analysis of KPM | journal=Archive for Mathematical Logic | volume=30 | year=1991 | pages=377–403 | doi=10.1007/BF01621475 | issue=5–6 | s2cid=9376863 }}
* {{cite journal | last=Rathjen | first=Michael | title=Proof theory of reflection | journal=Annals of Pure and Applied Logic | volume=68 | year=1994 | pages=181–224 | url=http://www.maths.leeds.ac.uk/~rathjen/ehab.pdf | doi=10.1016/0168-0072(94)90074-4 | issue=2 | archive-date=2020-10-21 | access-date=2008-05-10 | archive-url=https://web.archive.org/web/20201021105352/http://www1.maths.leeds.ac.uk/~rathjen/ehab.pdf | url-status=dead }}
* {{cite journal | last=Rathjen | first=Michael | title=Recent Advances in Ordinal Analysis: <math>\Pi^1_2</math>-CA and Related Systems | journal=The Bulletin of Symbolic Logic | volume=1 | year=1995 | pages=468–485 | url=
* {{cite journal | last=Kahle | first=Reinhard | title=Mathematical proof theory in the light of ordinal analysis | journal=Synthese | volume=133 | year=2002 | pages=237–255 | doi=10.1023/A:1020892011851 | s2cid=45695465 }}
* {{cite journal | last=Rathjen | first=Michael | title=An ordinal analysis of stability | journal=Archive for Mathematical Logic | volume=44 | year=2005 | pages=1–62 | url=http://www.maths.leeds.ac.uk/~rathjen/NSTAB.ps | doi=10.1007/s00153-004-0226-2 | citeseerx=10.1.1.15.9786 | s2cid=2686302 | archive-date=2022-12-20 | access-date=2008-05-10 | archive-url=https://web.archive.org/web/20221220161823/http://www1.maths.leeds.ac.uk/~rathjen/NSTAB.ps | url-status=dead }}
* {{cite web | url=http://www.mathematik.uni-muenchen.de/~aehlig/EST/rathjen4.pdf | title=Proof Theory: Part III,
{{countable ordinals}}
| |||