Ordinal collapsing function: Difference between revisions

Revision as of 22:56, 30 April 2022

Latest revision as of 19:30, 26 August 2025

(48 intermediate revisions by 21 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.

Line 4 ⟶ 6:

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 [[Kripke–Platek set theory]], [[Errett Bishop|Bishop]]-style systems of [[Constructivism (mathematics)|constructive mathematics]] or [[Per Martin-Löf|Martin-Löf]]-style systems of [[intuitionistic type theory]].

([[Psi (letter)|psi]])(1)

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

Line 35 ⟶ 36:

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 = \phi_1varphi_1(\alpha)</math> for all <math>\alpha\leq\zeta_0</math>, where <math>\zeta_0 = \varphi_2(0)</math> is the smallest fixed point of <math>\alpha \mapsto \varepsilon_\alpha</math>.

(Here, the <math>\varphi</math> functions are the [[Veblen function]]s defined starting with <math>\phi_1varphi_1(\alpha) = \varepsilon_\alpha</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>\varphi_1\colon \alpha\mapsto\varepsilon_\alpha</math> and thus never belongs to a <math>C(\alpha)</math> set for <math>\alpha\leq\Omega</math>, and the function <math>\psi</math> remains "stuck" at <math>\zeta_0</math> for some time:

Line 49 ⟶ 50:

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

The fact that <math>\psi(\Omega+\alpha)</math> =equals <math>\varepsilon_{\zeta_0+\alpha}</math> remains true for all <math>\alpha \leq \zeta_1 = \varphi_2(1)</math>. (noteNote, in particular, that <math>\psi(\Omega+\zeta_0) = \varepsilon_{\zeta_0\cdot2}</math>: but since now the ordinal <math>\zeta_0</math> has been constructed there is nothing to prevent from going beyond this). However, at <math>\zeta_1 = \phi_2varphi_2(1)</math> (the first fixed point of <math>\alpha\mapsto \varepsilon_\alpha</math> beyond <math>\zeta_0</math>), the construction stops again, because <math>\zeta_1</math> cannot be constructed from smaller ordinals and <math>\zeta_0</math> by finitely applying the <math>\varepsilon</math> function. So we have <math>\psi(\Omega \cdot 2) = \zeta_1</math>.

The same reasoning shows that <math>\psi(\Omega(1+\alpha)) = \phi_2varphi_2(\alpha)</math> for all <math>\alpha\leq\phi_3varphi_3(0) = \eta_0</math>, where <math>\phi_2varphi_2</math> enumerates the fixed points of <math>\phi_1varphi_1\colon\alpha\mapsto\varepsilon_\alpha</math> and <math>\phi_3varphi_3(0)</math> is the first fixed point of <math>\phi_2varphi_2</math>. We then have <math>\psi(\Omega^2) = \phi_3varphi_3(0)</math>.

Again, we can see that <math>\psi(\Omega^\alpha) = \varphi_{1+\alpha}(0)</math> for some time: this remains true until the first fixed point <math>\Gamma_0</math> of <math>\alpha \mapsto \phi_varphi_\alpha(0)</math>, which is the [[Feferman–Schütte ordinal]]. Thus, <math>\psi(\Omega^\Omega) = \Gamma_0</math> is the Feferman–Schütte ordinal.

==== Beyond the Feferman–Schütte ordinal ====

Line 66 ⟶ 67:

==== 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 "base <math>\delta</math> representation" is an obvious generalization of the [[Ordinal arithmetic#Cantor normal form|Cantor normal form]] (which is the case <math>\delta=\omega</math>). Of course, it may quite well be that the expression is uninteresting, i.e., <math>\alpha = \delta^\alpha</math>, but in any other case the <math>\beta_i</math> must all be less than <math>\alpha</math>; it may also be the case that the expression is trivial (i.e., <math>\alpha<\delta</math>, in which case <math>k\leq 1</math> and <math>\gamma_1 = \alpha</math>).

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

Line 99 ⟶ 100:

==== Conditions for canonicalness ====

The notations thus defined have the property that whenever they nest <math>\psi</math> functions, the arguments of the "inner" <math>\psi</math> function are always less than those of the "outer" one (this is a consequence of the fact that the <math>\Omega</math>-pieces of <math>\alpha</math>, where <math>\alpha</math> is the largest possible such that <math>\psi(\alpha)=\delta</math> for some <math>\varepsilon</math>-number <math>\delta</math>, are all less than <math>\delta</math>, as we have shown above). For example, <math>\psi(\psi(\Omega)+1)</math> does not occur as a notation: it is a well-defined expression (and it is equal to <math>\psi(\Omega) = \zeta_0</math> since <math>\psi</math> is constant between <math>\zeta_0</math> and <math>\Omega</math>), 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 <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 Feferman–Schütte ordinal: it can be written using the Veblen functions as <math>\varphi_1(\varphi_{\omega+1}(\varphi_2(0)) + \varphi_\omega(0)^{\varphi_3(0)}42)^{\varphi_1(1729)\,\omega}</math>.

Concerning the order, one might point out that <math>\psi(\Omega^\Omega)</math> (the Feferman–Schütte ordinal) is much more than <math>\psi(\Omega^{\psi(\Omega)}) = \varphi_{\varphi_2(0)}(0)</math> (because <math>\Omega</math> is greater than <math>\psi</math> of anything), and <math>\psi(\Omega^{\psi(\Omega)}) = \varphi_{\varphi_2(0)}(0)</math> is itself much more than <math>\psi(\Omega)^{\psi(\Omega)} = \varphi_2(0)^{\varphi_2(0)}</math> (because <math>\Omega^{\psi(\Omega)}</math> is greater than <math>\Omega</math>, so any sum-product-or-exponential expression involving <math>\psi(\Omega)</math> and smaller value will remain less than <math>\psi(\Omega^\Omega)</math>). In fact, <math>\psi(\Omega)^{\psi(\Omega)}</math> is already less than <math>\psi(\Omega+1)</math>.

Line 162 ⟶ 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) = \phi_2varphi_2(0)</math> and <math>\psi(\Omega^3) = \phi_3varphi_3(0)</math> and so on, but our construction ends there as there is no way to get at or beyond <math>\Omega^\omega</math>: so the range of this weakened system of notation is <math>\psi(\Omega^\omega) = \phi_\omega(0)</math> (the value of <math>\psi(\Omega^\omega)</math> 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 <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 = \phi_1varphi_1(\omega)</math>.

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 Bachmann–Howard ordinal ===

We know that <math>\psi(\varepsilon_{\Omega+1})</math> is the Bachmann–Howard ordinal. The reason why <math>\psi(\varepsilon_{\Omega+1}+1)</math> is no larger, with our definitions, is that there is no notation for <math>\varepsilon_{\Omega+1}</math> (it does not belong to <math>C(\alpha)</math> for any <math>\alpha</math>, it is always the least upper bound of it). One could try to add the <math>\varepsilon</math> 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 <math>\psi</math> function itself because it only yields countable ordinals (e.g., <math>\psi(\Omega+1)</math> is, <math>\varepsilon_{\phi_2varphi_2(0)+1}</math>, certainly not <math>\varepsilon_{\Omega+1}</math>), so the idea is to mimic its definition as follows:

:Let <math>\psi_1(\alpha)</math> be the smallest ordinal which cannot be expressed from all countable ordinals, <math>\Omega</math> and <math>\Omega_2</math> using sums, products, exponentials, and the <math>\psi_1</math> function itself (to previously constructed ordinals less than <math>\alpha</math>).

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) = \varepsilon_{\Omega+1}</math>, and more generally <math>\psi_1(\alpha) = \varepsilon_{\Omega+1+\alpha}</math> for all countable ordinals and even beyond (<math>\psi_1(\Omega) = \psi_1(\psi_1(0)) = \varepsilon_{\Omega 2}</math> and <math>\psi_1(\psi_1(01)) = \varepsilon_{\varepsilon_{\Omega+1}}</math>): this holds up to the first fixed point <math>\zeta_{\Omega+1}</math> beyond <math>\Omega</math> of the function <math>\xi\mapsto\varepsilon_\xi</math> functionbeyond <math>\Omega</math>, which is the limit of <math>\psi_1(0)</math>, <math>\psi_1(\psi_1(0))</math> and so forth. Beyond this, we have <math>\psi_1(\alpha) = \zeta_{\Omega+1}</math> and this remains true until <math>\Omega_2</math>: exactly as was the case for <math>\psi(\Omega)</math>, we have <math>\psi_1(\Omega_2) = \zeta_{\Omega+1}</math> and <math>\psi_1(\Omega_2+1) = \varepsilon_{\zeta_{\Omega+1}+1}</math>.

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 182 ⟶ 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(01))</math> &mdash; which is the Bachmann–Howard ordinal. But now we can get beyond this, and <math>\psi(\psi_1(01)+1)</math> is <math>\varepsilon_{\psi(\psi_1(01))+1}</math> (the next <math>\varepsilon</math>-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 <math>\Omega</math> and <math>\Omega_2</math> which are themselves defined using certain ordinals beyond <math>\Omega_2</math>.

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

Line 189 ⟶ 196:

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) "ordinal diagrams" of Takeuti<ref>Takeuti, 1967 (Ann. Math.)</ref> and <math>\theta</math> functions of Feferman: their range is the same (<math>\psi_0(\varepsilon_{\Omega_\omega+1})</math>, which could be called the Takeuti-Feferman–Buchholz ordinal, and which describes the [[ordinal analysis|strength]] of [[Second-order arithmetic#Stronger systems|<math>\Pi^1_1</math>-comprehension]] plus [[bar induction]]).

<!-- You can also have <math>\Omega</math> or more cardinals, in fact as many as nesting of the &psi; 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 209 ⟶ 220:

== 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 smallestleast <math>\mathsf{\Pi_NPi}^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 23</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_nomega_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_nomega_n(\mathbb{K}_N + 1))\}; n = 1, 2, \ldots</math> is [[Well-founded relation|well-founded]], and therefore, the [[Ordinal analysis|proof-theoretic ordinal]] of <math>\psi_\Omega(\varepsilon_{\mathbb{K}_N+1})</math> is the [[Ordinal analysis|proof-theoretic ordinal]] of <math>\mathsf{KP\Pi_N}</math>. Using this, <math>\psi_\Omega(\varepsilon_{\mathbb{K}_N+1}) = \min(\{\alpha \leq \Omega \mid \forall \theta \in \Sigma_1(\mathsf{KP\Pi_N} \vdash \theta^{L_\Omega} \rightarrow L_\alpha \models \theta)\})</math>. One can then make the following conversions:

* <math>\psi_{\Omega}(A) = \psi_0(varepsilon_{\Omega + 1}) = |\mathsf{PAKP\omega}| = \varphi(1, 0)mathsf{BHO}</math>, where <math>A\Omega</math> is either the least admissiblerecursively regular ordinal or the least uncountable cardinal, <math>\mathsf{PAKP\omega}</math> is [[PeanoKripke–Platek axioms|Peanoset arithmetictheory]] with infinity and <math>\varphimathsf{BHO}</math> is the [[VeblenBachmann–Howard function|Veblen hierarchyordinal]].

* <math>\psi_{\Omega(\varepsilon_{A +1}) = \psi_0(\varepsilon_Omega_{\Omega + 1omega}) = |\mathsf{KP\Pi^1_1-CA_0}| = \mathsf{BHOBO}</math>, where <math>A\Omega_{\omega}</math> is either the least limit of admissible ordinal,ordinals <math>\mathsf{KP}</math>or isthe [[Kripke–Platekleast setlimit theory]]of infinite cardinals and <math>\mathsf{BHOBO}</math> is the [[Bachmann–HowardBuchholz's ordinal]].

* <math>\psi_{\Omega}(I) = \psi_0(varepsilon_{\Omega_{\omega} + 1}) = |\mathsf{\Pi^1_1-CA_0KPl}| = \mathsf{BOTFBO}</math>, where <math>I\Omega_{\omega}</math> is either the least recursivelylimit inaccessibleof ordinaladmissible ordinals or the least limit of infinite cardinals, <math>\mathsf{KPl}</math> is KPi without the collection scheme and <math>\mathsf{BOTFBO}</math> is the [[Buchholz'sTakeuti–Feferman–Buchholz ordinal]].

* <math>\psi_{\Omega}(\varepsilon_{I +1}) = \psi_0(\varepsilon_{\Omega_\omega + 1}) = |\mathsf{KPIKPi}| = \mathsf{TFBO}</math>, where <math>I</math> is either the least recursively inaccessible ordinal, or the least weakly inaccessible cardinal and <math>\mathsf{KPIKPi}</math> is Kripke–Platek set theory with a recursively inaccessible universe and <math>\mathsf{TFBO}</math> is the [[Takeuti–Feferman–Buchholz ordinal]].

=== Bachmann's ''ψ'' ===

Line 223 ⟶ 234:

* 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 ''ψ'' ===

Line 234 ⟶ 245:

* 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) \andland \xi \in C_u(\xi) \andland 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>

Line 242 ⟶ 253:

=== 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, sometimes referred to as Extended Buchholz's ordinal. 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) \andland \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>

Line 267 ⟶ 278:

This function is only defined for arguments less than <math>\Omega^\omega</math>, and its outputs are limited by the small Veblen ordinal.

<math>\theta(1,2,\omega,\Omega)</math>

=== Jäger's ''ψ'' ===

Line 288 ⟶ 298:

* <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) \andland \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>

Line 299 ⟶ 309:

* M⁰ = <math>K \cap \mathsf{Lim}</math>, where Lim denotes the class of limit ordinals.

* For α > 0, M^α is the set <math>\{\pi < K \mid C(\alpha, \pi) \cap K = \pi \andland \forall \xi \in C(\alpha, \pi) \cap \alpha, M^\xi \mathsf{} </math> is stationary in <math>\pi \andland \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 \andland \pi \and, \alpha \in C(\alpha, \rho)\} \cup \{\pi\}) </math>.

=== Collapsing large cardinals ===

Line 311 ⟶ 321:

* 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 Kripke–Platek set theory augmented by certain [[reflection principle]]s (concentrating on the case of <math>\Pi_3</math>-reflection). Very roughly speaking, this proceeds by introducing the first cardinal <math>\Xi(\alpha)</math> which is <math>\alpha</math>-hyper-Mahlo and adding the <math>\alpha \mapsto \Xi(\alpha)</math> function itself to the collapsing system.

* 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 begun{{When|date=October 2018}}<ref>Rathjen, 2005 (Arch. Math. Logic)</ref> the investigation ofinvestigated 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 320 ⟶ 330:

* {{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&ndash;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&ndash;28 }}

* {{cite journal | last=Buchholz | first=Wilfried | title=A New System of Proof-Theoretic Ordinal Functions | journal=Annals of Pure and Applied Logic | volume=32 | year=1986 | pages=195&ndash;207 | doi=10.1016/0168-0072(86)90052-7 | url=https://epub.ub.uni-muenchen.de/3841/ | doi-access=free }}

* {{cite journal | last=Rathjen | first=Michael | title=Proof-theoretic analysis of KPM | journal=Archive for Mathematical Logic | volume=30 | year=1991 | pages=377&ndash;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&ndash;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&ndash;485 | url=https://www.math.ucla.edu/~asl/bsl/0104/0104-004.ps | doi=10.2307/421132 | jstor=421132 | issue=4 | s2cid=10648711 }}

* {{cite journal | last=Kahle | first=Reinhard | title=Mathematical proof theory in the light of ordinal analysis | journal=Synthese | volume=133 | year=2002 | pages=237&ndash;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&ndash;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, Kripke–Platek Set Theory | accessdate=2008-04-17 | last=Rathjen | first=Michael | date=August 2005 | archive-url=https://web.archive.org/web/20070612112202/http://www.mathematik.uni-muenchen.de/~aehlig/EST/rathjen4.pdf | archive-date=2007-06-12 | url-status=dead }}(slides of a talk given at Fischbachau)