In mathematics, ψ0(Ωω), 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 Π 1 1 {\displaystyle \Pi _{1}^{1}} -CA0 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 I D < ω {\displaystyle {\mathsf {ID_{<\omega }}}} , the theory of finitely iterated inductive definitions, and of K P ℓ 0 {\displaystyle 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 ω 0 {\displaystyle D_{0}D_{\omega }0} in Buchholz's ordinal notation ( O T , < ) {\displaystyle {\mathsf {(OT,<)}}} . Lastly, it can be expressed as the limit of the sequence: ε 0 = ψ 0 ( Ω ) {\displaystyle \varepsilon _{0}=\psi _{0}(\Omega )} , B H O = ψ 0 ( Ω 2 ) {\displaystyle {\mathsf {BHO}}=\psi _{0}(\Omega _{2})} , ψ 0 ( Ω 3 ) {\displaystyle \psi _{0}(\Omega _{3})} , ...
Definition
Ω 0 = 1 {\displaystyle \Omega _{0}=1} , and Ω n = ℵ n {\displaystyle \Omega _{n}=\aleph _{n}} for n > 0.
C i ( α ) {\displaystyle C_{i}(\alpha )} is the closure of Ω i {\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 } ).
ψ i ( α ) {\displaystyle \psi _{i}(\alpha )} is the smallest ordinal not in C i ( α ) {\displaystyle C_{i}(\alpha )} . Thus, ψ0(Ωω) is the smallest ordinal not in the closure of 1 {\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 } ).
References