View source for Buchholz's ordinal

{{Short description|Concept in mathematics}}
In mathematics, '''ψ<sub>0</sub>(Ω<sub>ω</sub>)''', widely known as '''Buchholz's ordinal'''{{citation needed|date=February 2024}}, is a [[large countable ordinal]] that is used to measure the [[proof-theoretic strength]] of some mathematical systems. In particular, it is the [[Ordinal analysis|proof theoretic ordinal]] of the subsystem <math>\Pi_1^1</math>-CA<sub>0</sub> of [[second-order arithmetic]];<ref name=":0">{{Cite journal|date=1986-01-01|title=A new system of proof-theoretic ordinal functions|url=https://dx.doi.org/10.1016/0168-0072%2886%2990052-7|journal=Annals of Pure and Applied Logic|language=en|volume=32|pages=195–207|doi=10.1016/0168-0072(86)90052-7|issn=0168-0072|last1=Buchholz |first1=W. |doi-access=free}}</ref><ref>{{Cite book|last=Simpson|first=Stephen G.|url=https://www.cambridge.org/core/books/subsystems-of-second-order-arithmetic/EA16CB4305831530B7015D6BC46B7424|title=Subsystems of Second Order Arithmetic|date=2009|publisher=Cambridge University Press|isbn=978-0-521-88439-6|edition=2|series=Perspectives in Logic|location=Cambridge}}</ref> this is one of the "big five" subsystems studied in [[reverse mathematics]] (Simpson 1999). It is also the proof-theoretic ordinal of <math>\mathsf{ID_{<\omega}}</math>, the theory of finitely [[Buchholz's ID hierarchy|iterated inductive definitions]], and of <math>KP\ell_0</math>,<ref>T. Carlson, "[https://people.math.osu.edu/carlson.6/research/patterns.pdf Elementary Patterns of Resemblance]" (1999). Accessed 12 August 2022.</ref> 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>D_0D_\omega0</math> in Buchholz's ordinal notation <math>\mathsf{(OT, <)}</math>.<ref name=":0" /> Lastly, it can be expressed as the limit of the sequence: <math>\varepsilon_0 = \psi_0(\Omega)</math>, <math>\mathsf{BHO} = \psi_0(\Omega_2)</math>, <math>\psi_0(\Omega_3)</math>, ... 

==Definition==
{{Main article|2 = Buchholz psi functions}}

* <math>\Omega_0 = 1</math>, and <math>\Omega_n  = \aleph_n</math> for ''n'' > 0.

* <math>C_i(\alpha)</math> is the closure of <math>\Omega_i</math> under addition and the <math>\psi_\eta(\mu)</math> function itself (the latter of which only for <math>\mu < \alpha</math> and <math>\eta \leq \omega</math>).
* <math>\psi_i(\alpha)</math> is the smallest ordinal not in <math>C_i(\alpha)</math>.
*Thus, ''ψ''<sub>0</sub>(Ω<sub>''ω''</sub>) is the smallest ordinal not in the closure of <math>1</math> under addition and the <math>\psi_\eta(\mu)</math> function itself (the latter of which only for <math>\mu < \Omega_\omega</math> and <math>\eta \leq \omega</math>).

==References==
{{reflist}}
{{refbegin}}
* G. Takeuti, ''Proof theory'', 2nd edition 1987 {{isbn|0-444-10492-5}}
* K. Schütte, ''Proof theory'', Springer 1977 {{isbn|0-387-07911-4}}
{{refend}}

{{countable ordinals}}

[[Category:Ordinal numbers]]
[[Category:Proof theory]]


{{Settheory-stub}}
{{number-stub}}