Buchholz's psi-functions: Difference between revisions
RhubarbJayde (talk | contribs) No edit summary |
CreeperBomb (talk | contribs) (Undo revision 696 by Cobsonwabag (talk)) Tag: Undo |
||
(7 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
Buchholz's \(\psi\)-functions are a family of functions \(\psi_\nu: |
Buchholz's \(\psi\)-functions are a family of functions \(\psi_\nu: \textrm{Ord}\to\textrm{Ord},\;\alpha\mapsto\psi_\nu(\alpha)\) defined by Wilfried Buchholz in 1984. |
||
==History== |
==History== |
||
<nowiki>In 1950, H. Bachmann defined the first ordinal collapsing function, Bachmann's \(\varphi\). While able to succinctly describe the Bachmann-Howard ordinal as \(\varphi_{\varepsilon_{\Omega+1}}(0)\)</nowiki><ref>W. Buchholz, [https://www.mathematik.uni-muenchen.de/~buchholz/articles/jaegerfestschr_buchholz3.pdf A survey on ordinal notations around the Bachmann-Howard ordinal]</ref>, Bachmann's \(\varphi\) had a complicated definition. Subsequently, Feferman made a simultaneous simplification and extension of Bachmann's \(\varphi\) up to the level of the [[Takeuti-Feferman-Buchholz ordinal]]<ref>W. Buchholz, Relating ordinals to proofs in a perspicuous way</ref><ref>S. Feferman, [https://math.stanford.edu/~feferman/papers/id-saga.pdf The proof theory of classical and constructive inductive definitions. A 40 year saga, 1968-2008.]</ref>, and then Buchholz further simplified Feferman's \( \theta \) to an ordinal collapsing function with behaviour more similar to the original by Bachmann.<ref>M. Rathjen, [https://www1.maths.leeds.ac.uk/~rathjen/ICMend.pdf The Art of Ordinal Analysis]</ref> |
<nowiki>In 1950, H. Bachmann defined the first ordinal collapsing function, Bachmann's \(\varphi\). While able to succinctly describe the Bachmann-Howard ordinal as \(\varphi_{\varepsilon_{\Omega+1}}(0)\)</nowiki><ref>W. Buchholz, [https://www.mathematik.uni-muenchen.de/~buchholz/articles/jaegerfestschr_buchholz3.pdf A survey on ordinal notations around the Bachmann-Howard ordinal]</ref>, Bachmann's \(\varphi\) had a complicated definition. Subsequently, Feferman made a simultaneous simplification and extension of Bachmann's \(\varphi\) up to the level of the [[Takeuti-Feferman-Buchholz ordinal]]<ref>W. Buchholz, Relating ordinals to proofs in a perspicuous way</ref><ref>S. Feferman, [https://math.stanford.edu/~feferman/papers/id-saga.pdf The proof theory of classical and constructive inductive definitions. A 40 year saga, 1968-2008.]</ref>, and then Buchholz further simplified Feferman's \( \theta \) to an ordinal collapsing function with behaviour more similar to the original by Bachmann.<ref>M. Rathjen, [https://www1.maths.leeds.ac.uk/~rathjen/ICMend.pdf The Art of Ordinal Analysis]</ref> |
||
Line 7: | Line 7: | ||
* \(C_\nu^0(\alpha) = \Omega_\nu\) |
* \(C_\nu^0(\alpha) = \Omega_\nu\) |
||
* \(C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma + \delta, \ |
* \(C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma + \delta, \psi_\mu(\xi): \gamma, \delta, \xi \in C_\nu^n(\alpha) \land \xi < \alpha \land \xi \in C_\mu(\xi) \land \mu \leq \omega\}\) |
||
* \(C_\nu(\alpha) = \bigcup\{C_\nu^n(\alpha): n < \omega\}\) |
* \(C_\nu(\alpha) = \bigcup\{C_\nu^n(\alpha): n < \omega\}\) |
||
* \(\psi_\nu(\alpha) = \operatorname{mex}(C_\nu(\alpha))\), where \(\ |
* \(\psi_\nu(\alpha) = \operatorname{mex}(C_\nu(\alpha))\), where \(\operatorname{mex}\) denotes minimal excludant. |
||
The limit of this system is \(\psi_0(\varepsilon_{\Omega_\omega+1})\), which is equal to the [[Takeuti-Feferman-Buchholz ordinal]]. This ordinal collapsing function admits a canonical associated ordinal notation, which was used to give an ordinal-analysis of the theory of \(\nu\)-times iterated inductive definitions for \(\nu \leq \omega\). Also, the ordinal notation admits a natural isomorphism to the set of Buchholz hydras. |
The limit of this system is \(\psi_0(\varepsilon_{\Omega_\omega+1})\), which is equal to the [[Takeuti-Feferman-Buchholz ordinal]]. The [[Buchholz ordinal]] is also defined in terms of this function, namely as \(\psi_0(\Omega_\omega)\). This ordinal collapsing function admits a canonical associated ordinal notation, which was used to give an ordinal-analysis of the theory of \(\nu\)-times iterated inductive definitions for \(\nu \leq \omega\). Also, the ordinal notation admits a natural isomorphism to the set of Buchholz hydras. |
||
== Extension == |
|||
This was extended by Denis Maksudov like so. We let \(\Omega_0 = 1\) and, for \(\nu > 0\), \(\Omega_\nu = \aleph_\nu\). Then: |
This was extended by Denis Maksudov like so. We let \(\Omega_0 = 1\) and, for \(\nu > 0\), \(\Omega_\nu = \aleph_\nu\). Then: |
||
* \(C_\nu^0(\alpha) = \Omega_\nu\) |
* \(C_\nu^0(\alpha) = \Omega_\nu\) |
||
* \(C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma + \delta, \ |
* \(C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma + \delta, \psi_\mu(\xi): \gamma, \delta, \mu, \xi \in C_\nu^n(\alpha) \land \xi < \alpha\}\) |
||
* \(C_\nu(\alpha) = \bigcup\{C_\nu^n(\alpha): n < \omega\}\) |
* \(C_\nu(\alpha) = \bigcup\{C_\nu^n(\alpha): n < \omega\}\) |
||
* \(\psi_\nu(\alpha) = \operatorname{mex}(C_\nu(\alpha))\), where \(\ |
* \(\psi_\nu(\alpha) = \operatorname{mex}(C_\nu(\alpha))\), where \(\operatorname{mex}\) denotes minimal excludant. |
||
The small difference is that we replace \(\mu \leq \omega\) with \(\mu \in C_\nu^n(\alpha)\), and remove \(\xi \in C_\mu(\xi)\). The limit of this new system is \(\psi_0(\Lambda)\), where \(\Lambda\) is the least ordinal so that \(\Omega_\Lambda = \Lambda\). |
The small difference is that we replace \(\mu \leq \omega\) with \(\mu \in C_\nu^n(\alpha)\), and remove \(\xi \in C_\mu(\xi)\). The limit of this new system is \(\psi_0(\Lambda)\), where \(\Lambda\) is the least ordinal so that \(\Omega_\Lambda = \Lambda\). The [[Bird ordinal]] and [[extended Buchholz ordinal]] are defined with this function. |
||
This admits an ordinal notation too, as well as a canonical set of fundamental sequences. |
This admits an ordinal notation too, as well as a canonical set of fundamental sequences. |
||
== References == |
Latest revision as of 16:54, 25 March 2024
Buchholz's \(\psi\)-functions are a family of functions \(\psi_\nu: \textrm{Ord}\to\textrm{Ord},\;\alpha\mapsto\psi_\nu(\alpha)\) defined by Wilfried Buchholz in 1984.
History[edit | edit source]
In 1950, H. Bachmann defined the first ordinal collapsing function, Bachmann's \(\varphi\). While able to succinctly describe the Bachmann-Howard ordinal as \(\varphi_{\varepsilon_{\Omega+1}}(0)\)[1], Bachmann's \(\varphi\) had a complicated definition. Subsequently, Feferman made a simultaneous simplification and extension of Bachmann's \(\varphi\) up to the level of the Takeuti-Feferman-Buchholz ordinal[2][3], and then Buchholz further simplified Feferman's \( \theta \) to an ordinal collapsing function with behaviour more similar to the original by Bachmann.[4]
Definition[edit | edit source]
We let \(\Omega_0 = 1\) and, for \(\nu > 0\), \(\Omega_\nu = \aleph_\nu\). Then:
- \(C_\nu^0(\alpha) = \Omega_\nu\)
- \(C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma + \delta, \psi_\mu(\xi): \gamma, \delta, \xi \in C_\nu^n(\alpha) \land \xi < \alpha \land \xi \in C_\mu(\xi) \land \mu \leq \omega\}\)
- \(C_\nu(\alpha) = \bigcup\{C_\nu^n(\alpha): n < \omega\}\)
- \(\psi_\nu(\alpha) = \operatorname{mex}(C_\nu(\alpha))\), where \(\operatorname{mex}\) denotes minimal excludant.
The limit of this system is \(\psi_0(\varepsilon_{\Omega_\omega+1})\), which is equal to the Takeuti-Feferman-Buchholz ordinal. The Buchholz ordinal is also defined in terms of this function, namely as \(\psi_0(\Omega_\omega)\). This ordinal collapsing function admits a canonical associated ordinal notation, which was used to give an ordinal-analysis of the theory of \(\nu\)-times iterated inductive definitions for \(\nu \leq \omega\). Also, the ordinal notation admits a natural isomorphism to the set of Buchholz hydras.
Extension[edit | edit source]
This was extended by Denis Maksudov like so. We let \(\Omega_0 = 1\) and, for \(\nu > 0\), \(\Omega_\nu = \aleph_\nu\). Then:
- \(C_\nu^0(\alpha) = \Omega_\nu\)
- \(C_\nu^{n+1}(\alpha) = C_\nu^n(\alpha) \cup \{\gamma + \delta, \psi_\mu(\xi): \gamma, \delta, \mu, \xi \in C_\nu^n(\alpha) \land \xi < \alpha\}\)
- \(C_\nu(\alpha) = \bigcup\{C_\nu^n(\alpha): n < \omega\}\)
- \(\psi_\nu(\alpha) = \operatorname{mex}(C_\nu(\alpha))\), where \(\operatorname{mex}\) denotes minimal excludant.
The small difference is that we replace \(\mu \leq \omega\) with \(\mu \in C_\nu^n(\alpha)\), and remove \(\xi \in C_\mu(\xi)\). The limit of this new system is \(\psi_0(\Lambda)\), where \(\Lambda\) is the least ordinal so that \(\Omega_\Lambda = \Lambda\). The Bird ordinal and extended Buchholz ordinal are defined with this function.
This admits an ordinal notation too, as well as a canonical set of fundamental sequences.
References[edit | edit source]
- ↑ W. Buchholz, A survey on ordinal notations around the Bachmann-Howard ordinal
- ↑ W. Buchholz, Relating ordinals to proofs in a perspicuous way
- ↑ S. Feferman, The proof theory of classical and constructive inductive definitions. A 40 year saga, 1968-2008.
- ↑ M. Rathjen, The Art of Ordinal Analysis