Ordinal collapsing function: Difference between revisions

Revision as of 21:05, 28 March 2024

Latest revision as of 19:30, 26 August 2025

(12 intermediate revisions by 8 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 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 = \phi_2varphi_2(0)</math> is the smallest fixed point of <math>\alpha \mapsto \varepsilon_\alpha</math>.

(Here, the <math>\phivarphi</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>\phi_1varphi_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:

:<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 ("artificially") added to all the <math>C(\alpha)</math>, we are permitted to take the value <math>\psi(\Omega) = \zeta_0</math> in the process. So <math>C(\Omega+1)</math> contains all ordinals which can be built from <math>0</math>, <math>1</math>, <math>\omega</math>, <math>\Omega</math>, the <math>\phi_1varphi_1\colon\alpha\mapsto\varepsilon_\alpha</math> function ''up to <math>\zeta_0</math>'' and this time also <math>\zeta_0</math> itself, using addition, multiplication and exponentiation. The smallest ordinal not in <math>C(\Omega+1)</math> is <math>\varepsilon_{\zeta_0+1}</math> (the smallest <math>\varepsilon</math>-number after <math>\zeta_0</math>).

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 ''ψ'' 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 = \phi_2varphi_2(1)</math>. (Note, 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) = \phi_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 ====

We have <math>\psi(\Omega^\Omega+\Omega^\alpha) = \phi_varphi_{\Gamma_0+\alpha}(0)</math> for all <math>\alpha\leq\Gamma_1</math> where <math>\Gamma_1</math> is the next fixed point of <math>\alpha \mapsto \phi_varphi_\alpha(0)</math>. So, if <math>\alpha\mapsto\Gamma_\alpha</math> enumerates the fixed points in question (which can also be noted <math>\phivarphi(1,0,\alpha)</math> using the many-valued Veblen functions) we have <math>\psi(\Omega^\Omega(1+\alpha)) = \Gamma_\alpha</math>, until the first fixed point <math>\phivarphi(1,1,0)</math> of the <math>\alpha\mapsto\Gamma_\alpha</math> itself, which will be <math>\psi(\Omega^{\Omega+1})</math> (and the first fixed point <math>\phivarphi(2,0,0)</math> of the <math>\alpha \mapsto \phivarphi(1,\alpha,0)</math> functions will be <math>\psi(\Omega^{\Omega\cdot 2})</math>). In this manner:

* <math>\psi(\Omega^{\Omega^2})</math> is the [[Ackermann ordinal]] (the range of the notation <math>\phivarphi(\alpha,\beta,\gamma)</math> defined predicatively),

* <math>\psi(\Omega^{\Omega^\omega})</math> is the [[small Veblen ordinal|"small" Veblen ordinal]] (the range of the notations <math>\phivarphi(\cdot)</math> predicatively using finitely many variables),

* <math>\psi(\Omega^{\Omega^\Omega})</math> is the [[large Veblen ordinal|"large" Veblen ordinal]] (the range of the notations <math>\phivarphi(\cdot)</math> predicatively using transfinitely-but-predicatively-many variables),

* 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 [[Bachmann–Howard ordinal]]: after this our function <math>\psi</math> is constant, and we can go no further with the definition we have given.

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 100 ⟶ 101:

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

Line 223 ⟶ 224:

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}(\Omega) = |\mathsf{PA}| = \varphi(1, 0)</math>, where <math>\Omega</math> is either the least recursively regular ordinal or the least uncountable cardinal, <math>\mathsf{PA}</math> is [[Peano axioms|Peano arithmetic]] and <math>\varphi</math> is the [[Veblen function|Veblen hierarchy]].

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

Line 236:

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

Line 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 332:

* {{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)