Buchholz's ordinal

In mathematics, ψ₀(Ω_ω), widely known as Buchholz's ordinal^{[citation needed]}, is a large countable ordinal that is used to measure the proof-theoretic strength of some mathematical systems. In particular, it is the proof theoretic ordinal of the subsystem $\Pi _{1}^{1}$ -CA₀ of second-order arithmetic;^[1]^[2] this is one of the "big five" subsystems studied in reverse mathematics (Simpson 1999). It is also the proof-theoretic ordinal of ${\mathsf {ID_{<\omega }}}$ , the theory of finitely iterated inductive definitions, and of $KP\ell _{0}$ ,^[3] a fragment of Kripke-Platek set theory extended by an axiom stating every set is contained in an admissible set. Buchholz's ordinal is also the order type of the segment bounded by $D_{0}D_{\omega }0$ in Buchholz's ordinal notation ${\mathsf {(OT,<)}}$ .^[1] Lastly, it can be expressed as the limit of the sequence: $\varepsilon _{0}=\psi _{0}(\Omega )$ , ${\mathsf {BHO}}=\psi _{0}(\Omega _{2})$ , $\psi _{0}(\Omega _{3})$ , ...

Definition

$\Omega _{0}=1$ , and $\Omega _{n}=\aleph _{n}$ for n > 0.

$C_{i}(\alpha )$ is the closure of $\Omega _{i}$ under addition and the $\psi _{\eta }(\mu )$ function itself (the latter of which only for $\mu <\alpha$ and $\eta \leq \omega$ ).
$\psi _{i}(\alpha )$ is the smallest ordinal not in $C_{i}(\alpha )$ .
Thus, ψ₀(Ω_ω) is the smallest ordinal not in the closure of $1$ under addition and the $\psi _{\eta }(\mu )$ function itself (the latter of which only for $\mu <\Omega _{\omega }$ and $\eta \leq \omega$ ).

References

^ ^a ^b Buchholz, W. (1986-01-01). "A new system of proof-theoretic ordinal functions". Annals of Pure and Applied Logic. 32: 195–207. doi:10.1016/0168-0072(86)90052-7. ISSN 0168-0072.
^ Simpson, Stephen G. (2009). Subsystems of Second Order Arithmetic. Perspectives in Logic (2 ed.). Cambridge: Cambridge University Press. ISBN 978-0-521-88439-6.
^ T. Carlson, "Elementary Patterns of Resemblance" (1999). Accessed 12 August 2022.