Ψ₀(Ω_ω)

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

Definition

Main article: Ordinal collapsing function

• ${\displaystyle \Omega _{0}=0}$, and ${\displaystyle \Omega _{n}=\aleph _{n}}$ for n > 0.
• ${\displaystyle C_{i}(\alpha )}$ is the smallest set of ordinals that contains ${\displaystyle \Omega _{n}}$ for n finite, and contains all ordinals less than ${\displaystyle \Omega _{i}}$, and is closed under ordinal addition and exponentiation, and contains ${\displaystyle \Psi _{j}(\xi )}$ if j ≥ i and ${\displaystyle \xi \in C_{i}(\alpha )}$ and ${\displaystyle \xi <\alpha }$.
• ${\displaystyle \Psi _{i}(\alpha )}$ is the smallest ordinal not in ${\displaystyle 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, MR 2517689