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 ${\displaystyle \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 ${\displaystyle {\mathsf {ID_{<\omega }}}}$, the theory of finitely iterated inductive definitions, and of ${\displaystyle 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 ${\displaystyle D_{0}D_{\omega }0}$ in Buchholz's ordinal notation ${\displaystyle {\mathsf {(OT,<)}}}$.^[1] Lastly, it can be expressed as the limit of the sequence: ${\displaystyle \varepsilon _{0}=\psi _{0}(\Omega )}$, ${\displaystyle {\mathsf {BHO}}=\psi _{0}(\Omega _{2})}$, ${\displaystyle \psi _{0}(\Omega _{3})}$, ...

Definition

Main article: Buchholz psi functions

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

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