Ordinal collapsing function: Difference between revisions

Revision as of 06:09, 23 November 2022

Latest revision as of 19:30, 26 August 2025

(31 intermediate revisions by 16 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 5 ⟶ 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 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 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 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 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 169:

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 = \varphi_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.

Line 218 ⟶ 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 234 ⟶ 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 243 ⟶ 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) \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>

Line 251 ⟶ 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 310 ⟶ 312:

* <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 \land, \alpha \in C(\alpha, \rho)\} \cup \{\pi\}) </math>.

=== Collapsing large cardinals ===

Line 319 ⟶ 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 328 ⟶ 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)