Ordinal collapsing function: Difference between revisions
Jump to navigation
Jump to search
Content added Content deleted
(Possibly less confusing wording) |
(→List) |
||
| Line 15: | Line 15: | ||
== Remarks == |
== 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> |
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> |
||
== 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 == |
== List == |
||
| Line 21: | Line 24: | ||
* Feferman's \( \theta \)-functions |
* Feferman's \( \theta \)-functions |
||
* [[Buchholz's psi-functions|Buchholz's \( \psi \)-functions]], a simplification of 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 |
* 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 |
* Madore's \( \psi \)-function, a further simplification of Buchholz's \( \psi \)-functions |
||
* Bird's \( \theta \)-function |
* Bird's \( \theta \)-function |
||
* Weiermann's \( \vartheta \), a variant of Buchholz's \( \psi \)-functions with nicer behaviour |
* Weiermann's \( \vartheta \), a variant of Buchholz's \( \psi \)-functions with nicer behaviour |
||
* Wilken's \( \vartheta \) & Wilken and Weiermann's \( \bar{\vartheta} \), variants of Weiermann's \( \vartheta \) |
* 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]] |
* 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 |
* The Jäger-Buchholz function, a simplification of Jäger's \( \psi \)-function |
||