Ψ₀(Ωω)

In mathematics, Ψ₀(Ω_ω) 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 ${\mathrm{\Pi }}_1^1$-CA₀ of second-order arithmetic; this is one of the "big five" subsystems studied in reverse mathematics (Simpson 1999).

Definition

• ${\mathrm{\Omega }}_0=0$, and ${\mathrm{\Omega }}_n={\mathrm{\aleph }}_n$ for n > 0.
• $C_i(\alpha )$ is the smallest set of ordinals that contains ${\mathrm{\Omega }}_n$ for n finite, and contains all ordinals less than ${\mathrm{\Omega }}_i$, and is closed under ordinal addition and exponentiation, and contains ${\mathrm{\Psi }}_j(\xi )$ if j ≥ i and $\xi \in C_i(\alpha )$ and $\xi <\alpha$.
• ${\mathrm{\Psi }}_i(\alpha )$ is the smallest ordinal not in $C_i(\alpha )$

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
• Simpson, Stephen G. (2009), Subsystems of second order arithmetic, Perspectives in Logic (2nd ed.), Cambridge University Press, ISBN 978-0-521-88439-6, http://www.math.psu.edu/simpson/sosoa/