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

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)\), 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, and then Buchholz further simplified Feferman's \( \theta \) to an ordinal collapsing function with behaviour more similar to the original by Bachmann.

Definition

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

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.