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;[1][2] 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}$ ,[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 $D_{0}D_{\omega }0$ in Buchholz's ordinal notation ${\mathsf {(OT,<)}}$ .[1] 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

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

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.
Simpson, Stephen G. (2009). Subsystems of Second Order Arithmetic. Perspectives in Logic (2 ed.). Cambridge: Cambridge University Press. ISBN 978-0-521-88439-6.
T. Carlson, Elementary Patterns of Resemblance (1999). Accessed 12 August 2022.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[:0-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.