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

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

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

• Ordinal numbers
• Proof theory
• Set theory stubs
• Number stubs

• Articles with short description
• Short description is different from Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from February 2024
• All stub articles