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 ${\mathrm{\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{I}{\mathsf{D}}_{<\mathsf{\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{(}\mathsf{O}\mathsf{T},<\mathsf{)}$. Lastly, it can be expressed as the limit of the sequence: ${\epsilon }_0={\psi }_0(\mathrm{\Omega })$, $\mathsf{B}\mathsf{H}\mathsf{O}={\psi }_0({\mathrm{\Omega }}_2)$, ${\psi }_0({\mathrm{\Omega }}_3)$, ...

Definition

• ${\mathrm{\Omega }}_0=1$, and ${\mathrm{\Omega }}_n={\mathrm{\aleph }}_n$ for n > 0.

• $C_i(\alpha )$ is the closure of ${\mathrm{\Omega }}_i$ under addition and the ${\psi }_{\eta }(\mu )$ function itself (the latter of which only for $\mu <\alpha$ and $\eta \le \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 <{\mathrm{\Omega }}_{\omega }$ and $\eta \le \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