Using Buchholz's function, the ordinal \(\psi_0(\Omega_{\omega})\) is a large countable ordinal that is the proof theoretic ordinal of \(\Pi_1^1\)-\(\text{CA}_0\)[1], a subsystem[2] of second-order arithmetic.
In googology, the ordinal is widely called Buchholz's ordinal or BO.[3] Readers should be careful that Buchholz's ordinal is different from Takeuti-Feferman-Buchholz ordinal. The abbreviation to \(\psi\) was originally invented by Rathjen and Weiermann to express the restriction \(\psi_0 |_{\varepsilon_{\Omega+1}}\),[4] of \(\psi\), but somewhy several googologists tend to use the same abbreviation to express the full \(\psi_0\) and other sorts of ordinal collapsing functions with indices under confusion of them.
Property[]
It is the order type of the segment bounded by \(D_0 D_{\omega} 0\) in Buchholz's ordinal notation \((OT,<)\).
The subcubic graphs, which are used in definition of SCG function, can be ordered so that we can make bijection between them and ordinals below \(\psi_0(\Omega_{\omega})\), as well as Buchholz hydras with \(\omega\) labels removed. Bird stated that SCG function and Buchholz hydras with \(\omega\) labels removed are both approximated to \(\psi_0(\Omega_{\omega})\) in the fast-growing hierarchy.[5] Since there is no actual proof, it might be based on a wrong belief that a notation which can "express" ordinals below a fixed ordinal \(\alpha\) gives a function approximated to \(\alpha\) in the fast-growing hierarchy with respect to some system of fundamental sequence (counterexamples to this belief exist, e.g. Irrational arrow notation).
Also, it is verified by a Japanese Googology Wiki user p進大好きbot that each standard pair sequence \(M\) corresponds to an ordinal \(\textrm{Trans}(M)\) below \(\psi_0(\Omega_{\omega})\) so that the expansion expansion of \(M\) gives a strictly increasing sequence of ordinals below \(\textrm{Trans}(M)\).[6] In particular, it implies that pair sequence system restricted to standard pair sequences gives a total computable function whose stractural well-ordering is of order type bounded by \(\psi_0(\Omega_{\omega})\). It is also strongly believed in this community that the structural well-ordering is of order type \(\psi_0(\Omega_{\omega})\).
Common misconception[]
It is believed to be the first ordinal \(\alpha\) for which \(g_{\alpha}(n)\) in the slow-growing hierarchy "catches up" with \(f_{\alpha}(n)\) the fast-growing hierarchy in this community, but the statement is just a common mistake as p進大好きbot pointed out.[7] The ambiguous statement itself is not meaningful unless we fix the definitions of a comparability and a system of fundamental sequences applicable to ordinals including \(\psi_0(\Omega_{\omega})\), although the choices are often omitted. For example, \(\omega\) is also the first ordinal \(\alpha\) for which \(g_{\alpha}(n)\) in the slow-growing hierarchy "catches up" with \(f_{\alpha}(n)\) the fast-growing hierarchy in some sense under a certain system of fundamental sequences.
Sources[]
- ↑ W. Buchholz, A new system of proof-theoretic ordinal functions (1984). Retrieved 2021-06-19.
- ↑ S. Simpson, Subsustems of Second-Order Arithmetic, 2009
- ↑ Fish, Abbreviation, Googology Wiki user page.
- ↑ W. Buchholz, A survey on ordinal notations around the Bachmann-Howard ordinal (p.18)
- ↑ Bird, Chris. Fast-Growing Hierarchy in terms of Bird's Array Notation
- ↑ p進大好きbot, ペア数列の停止性, Japanese Googology Wiki user blog.
- ↑ p進大好きbot, List of common mistakes in googology/FGH/Is the least catching ordinal well-defined?, Googology Wiki user blog.
See also[]
Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation · Absolute infinity
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function) · \(\omega_1^\mathfrak{Ch}\) (Omega one of chess) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\gamma,\zeta,\Sigma\) (Infinite time Turing machine ordinals) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Hardy hierarchy · Slow-growing hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Weak Buchholz's function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Weak Buchholz's function · Extended Buchholz's function · Jäger-Buchholz function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function · Arai's psi function
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal
Classes: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)