Misplaced Pages

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 ${\displaystyle \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 ${\displaystyle {\mathsf {ID_{<\omega }}}}$, the theory of finitely iterated inductive definitions, and of ${\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 ${\displaystyle D_{0}D_{\omega }0}$ in Buchholz's ordinal notation ${\displaystyle {\mathsf {(OT,<)}}}$. 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

• ${\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 }$).

References

1. ^ Buchholz, W. (1986-01-01). "A new system of proof-theoretic ordinal functions". Annals of Pure and Applied Logic. 32: 195–207. doi:10.1016/0168-0072(86)90052-7. ISSN 0168-0072.
2. Simpson, Stephen G. (2009). Subsystems of Second Order Arithmetic. Perspectives in Logic (2 ed.). Cambridge: Cambridge University Press. ISBN 978-0-521-88439-6.
3. T. Carlson, "Elementary Patterns of Resemblance" (1999). Accessed 12 August 2022.

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

This set theory-related article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

This article about a number is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

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