Buchholz's psi-functions
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