Buchholz's ordinal
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 [math]\displaystyle{ \Pi_1^1 }[/math]-CA0 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 [math]\displaystyle{ \mathsf{ID_{\lt \omega}} }[/math], the theory of finitely iterated inductive definitions, and of [math]\displaystyle{ KP\ell_0 }[/math],[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 [math]\displaystyle{ D_0D_\omega0 }[/math] in Buchholz's ordinal notation [math]\displaystyle{ \mathsf{(OT, \lt )} }[/math].[1] Lastly, it can be expressed as the limit of the sequence: [math]\displaystyle{ \varepsilon_0 = \psi_0(\Omega) }[/math], [math]\displaystyle{ \mathsf{BHO} = \psi_0(\Omega_2) }[/math], [math]\displaystyle{ \psi_0(\Omega_3) }[/math], ...
Definition
- [math]\displaystyle{ \Omega_0 = 1 }[/math], and [math]\displaystyle{ \Omega_n = \aleph_n }[/math] for n > 0.
- [math]\displaystyle{ C_i(\alpha) }[/math] is the closure of [math]\displaystyle{ \Omega_i }[/math] under addition and the [math]\displaystyle{ \psi_\eta(\mu) }[/math] function itself (the latter of which only for [math]\displaystyle{ \mu \lt \alpha }[/math] and [math]\displaystyle{ \eta \leq \omega }[/math]).
- [math]\displaystyle{ \psi_i(\alpha) }[/math] is the smallest ordinal not in [math]\displaystyle{ C_i(\alpha) }[/math].
- Thus, ψ0(Ωω) is the smallest ordinal not in the closure of [math]\displaystyle{ 1 }[/math] under addition and the [math]\displaystyle{ \psi_\eta(\mu) }[/math] function itself (the latter of which only for [math]\displaystyle{ \mu \lt \Omega_\omega }[/math] and [math]\displaystyle{ \eta \leq \omega }[/math]).
References
- ↑ 1.0 1.1 Buchholz, W. (1986-01-01). "A new system of proof-theoretic ordinal functions" (in en). Annals of Pure and Applied Logic 32: 195–207. doi:10.1016/0168-0072(86)90052-7. ISSN 0168-0072. https://dx.doi.org/10.1016/0168-0072%2886%2990052-7.
- ↑ Simpson, Stephen G. (2009). Subsystems of Second Order Arithmetic. Perspectives in Logic (2 ed.). Cambridge: Cambridge University Press. ISBN 978-0-521-88439-6. https://www.cambridge.org/core/books/subsystems-of-second-order-arithmetic/EA16CB4305831530B7015D6BC46B7424.
- ↑ 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
 |  |
