Ordinal collapsing function: Difference between revisions
→History
(Possibly less confusing wording) |
IDoNotExist (talk | contribs) |
||
| (12 intermediate revisions by one other user not shown) | |||
Line 4:
== History ==
The first ordinal collapsing function in the literature was Bachmann's \( \
A modern "recast", proposed by Michael Rathjen<ref name="RathjenArt">Rathjen, Michael. "[https://www1.maths.leeds.ac.uk/~rathjen/ICMend.pdf The Art of Ordinal Analysis]".</ref>, is that \( \psi_\Omega(\alpha)\) is the least countable \( \rho \) so that the countable ordinals constructible from \(\Omega\) and the set of ordinals below \( \max(1, \rho) \) using the following operations are all less than \(\rho\): addition, the map \( \xi \mapsto \omega^\xi \), and \( \psi_\Omega \) restricted to inputs less than \( \alpha \). Of course, this definition is condensed, and is usually written in terms of \( C \)-sets. Below is the more formal definition.
* Let \( \Omega = \aleph_1 \) and \( C_0^\Omega(\alpha, \beta) = \beta \cup \{0, \Omega\} \).
Line 15 ⟶ 17:
== Remarks ==
Rathjen has remarked upon a small detail of various ordinal collapsing functions, which he calls pictorial collapse. In particular, he says that, in the OCF defined in the "History" section, \( \psi_\Omega(\alpha) \) can be viewed as the "\( \alpha \)th collapse of \( \Omega \)" since, as he puts it, the order-type of \( \Omega \) as viewed within \( C^\Omega(\alpha, \psi_\Omega(\alpha)) \) is actually \( \psi_\Omega(\alpha) \).<ref>M. Rathjen, Proof Theory (Stanford encyclopedia of Philosophy), special case of definition 5.11</ref> The same property applies to [[Buchholz's psi-functions]]<ref>W. Buchholz, ''A New System of Proof-Theoretic Ordinal Functions'', Annals of Pure and Applied Logic, vol. 32, pp.195-207, (1986)</ref>, Rathjen's OCF collapsing a [[Mahlo cardinal|weakly Mahlo cardinal]]<ref>Rathjen, Michael. "Ordinal Notations Based on a Weakly Mahlo Cardinal", Archive for Mathematical Logic 29 (1990) 249--263.</ref>, and Rathjen's OCF collapsing a [[weakly compact cardinal]].<ref>Rathjen, Michael. "Proof Theory of Reflection", Annals of Pure and Applied Logic 68, 181--224 (1994).</ref>
== Use of nonrecursive countable ordinals ==
It may seem circular to use an OCF whose definition presumes existence of uncountable or large cardinals in the ordinal analysis of a theory much weaker than ZFC. However all instances of uncountable cardinals in the definition of the OCF may be replaced with nonrecursive countable ordinals, at the expense of much difficulty in proving the relevant theorems about the OCF. For example, Rathjen has defined an OCF for analyzing KPM that uses [[Admissible ordinal|admissible ordinals]] in place of regular cardinals, and recursively Mahlo ordinals in place of Mahlo cardinals.<ref>Realm of Ordinal Analysis, near the end</ref>
The main technique for proving the relevant theorems about \( \psi_\pi(\alpha) \) (e.g. that \( \psi_\pi(\alpha)<\pi \)) becomes to use a \( \pi \)-recursive coding scheme to code the representable ordinals that are \( >\pi \) into members of \( L_\pi \). This coding must respect the ordering of the \( \psi_\kappa(\beta) \), which itself has not yet been verified.<ref name="Rathjen94">Possible citation? [https://www1.maths.leeds.ac.uk/~rathjen/WELL.pdf]</ref><sup>Maybe not? Look at things around p.11 more</sup><!--This citation is for previous sentence also--> This is in contrast to the cardinal-based definition of \( \psi \), in which case these can be proven by simple arguments like cardinality arguments.<ref>M. Rathjen, "How to develop proof-theoretic ordinal functions on the basis of admissible ordinals" (1998), MSC-1991 classification 03F13/03F35. Accessed 1 September 2023. Possibly in Mathematical Quarterly vol. 39 (1993)?</ref> In addition, some of the relations recursive definitions are performed along are well-founded but non-set-like.<ref name="Rathjen94" /><sup>p.5</sup>
== Quantifier complexity ==
The quantifier complexity of many OCFs seems to be \( \Sigma_1 \). This holds for Buchholz's and Bachmann's OCFs,<ref>The only citation I have is a Discord message, https://discord.com/channels/206932820206157824/655959490755035169/861665386705059870</ref> and Arai's OCF for \( \Pi_n \)-reflection.<ref>T. Arai, "[https://arxiv.org/abs/1907.07611v1 A simplified ordinal analysis of first-order reflection]", proposition 2.7. arXiv version (2019), accessed 31 August 2023.</ref> The quantifier complexity of Arai's OCF for \( \textsf{KP}\ell^r+\exists M(\textrm{isTrans}(M)\land M\prec_{\Sigma_1}V) \) is \( \Delta_1 \),<ref>T. Arai, "[https://arxiv.org/abs/2208.12944 An ordinal analysis of a single stable ordinal]", proposition 2.11. arXiv version (2023), accessed 31 August 2023.</ref> however the quantifier complexity of Arai's OCF for KP+\( \Pi_1 \)-collection is \( \Delta_1(St) \).<ref>T. Arai, "[https://arxiv.org/abs/2112.09871 An ordinal analysis of \(\Pi_1\)-Collection]", proposition 3.8. arXiv version (2023), accessed 31 August 2023.</ref>
== List ==
Line 21 ⟶ 31:
* Feferman's \( \theta \)-functions
* [[Buchholz's psi-functions|Buchholz's \( \psi \)-functions]], a simplification of Feferman's \( \theta \)-functions
* Schütte and Simpson's addition-free versions of Buchholz's functions, denoted \( \pi_i \)<ref name="VanDerMeeren15">J. Van der Meeren, "[https://core.ac.uk/download/pdf/55770155.pdf Connecting the Two Worlds: Well-partial-orders and Ordinal Notation Systems]". PhD dissertation (2015), accessed 31 August 2023.</ref><sup>pp.20--23</sup>
* Gordeev's \( D_\nu \) functions<ref name="VanDerMeeren15" /><sup>pp.2--3</sup>
* Maksudov's extended Buchholz \( \psi \)-functions, an extension of Buchholz's \( \psi \)-functions
* Madore's \( \psi \)-function, a further simplification of Buchholz's \( \psi \)-functions
* Bird's \( \theta \)-function
* Weiermann's \( \vartheta \), a variant of Buchholz's \( \psi \)-functions with nicer behaviour
* Wilken's \( \vartheta \), which does not need standard forms,<ref>G. Wilken, "[https://www.sciencedirect.com/science/article/pii/S0168007206001175 Ordinal arithmetic based on Skolem hulling]", p.131. Annals of Pure and Applied Logic vol. 145, iss. 2 (2007), pp.130--161.</ref> & Wilken and Weiermann's \( \bar{\vartheta} \), variants of Weiermann's \( \vartheta \)
* Jäger's \( \psi \)-function, an extension of Bachmann's \( \psi \) to the level of [[Inaccessible cardinal|weakly inaccessible cardinals]]
* The Jäger-Buchholz function, a simplification of Jäger's \( \psi \)-function
| |||