Buchholz's ordinal

In mathematics, ψ₀(Ω_ω), widely known as Buchholz's ordinal, 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; 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}$, 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,<)}}$. 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

Main article: Buchholz psi functions

• $\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

• G. Takeuti, Proof theory, 2nd edition 1987 ISBN 0-444-10492-5
• K. Schütte, Proof theory, Springer 1977 ISBN 0-387-07911-4