Content deleted Content added
Rescuing 2 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
|||
| (46 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]].
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 = \
(Here, the <math>\varphi</math> functions are the [[Veblen function]]s defined starting with <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>
The same reasoning shows that <math>\psi(\Omega(1+\alpha)) = \
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 \
==== 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 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 168 ⟶ 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.
=== 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_{\
: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 185 ⟶ 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
Line 192 ⟶ 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 ψ 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 212 ⟶ 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
Suppose <math>\mathsf{KP\Pi_N} \vdash \theta
* <math>\psi_{\Omega}(
* <math>\psi_{\Omega
* <math>\psi_{\Omega}(
* <math>\psi_{\Omega}(\varepsilon_{I
=== Bachmann's ''ψ'' ===
Line 226 ⟶ 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 237 ⟶ 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) \
* <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 245 ⟶ 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
* 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) \
* <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 270 ⟶ 278:
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 ''ψ'' ===
Line 291 ⟶ 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) \
* <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 302 ⟶ 309:
* 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 \
* <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 \
=== Collapsing large cardinals ===
Line 314 ⟶ 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
== Notes ==
Line 323 ⟶ 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–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 Functions | journal=Annals of Pure and Applied Logic | volume=32 | year=1986 | pages=195–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–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=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–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, 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)
| |||