← All problems

Wikipedia model theory and formal languages item 24: What is the nature of the proof-theoretic ordinal (the smallest ordinal a theory cannot prove w…

50 years old · documented by

The question is: “What is the nature of the proof-theoretic ordinal (the smallest ordinal a theory cannot prove well-founded) for second-order arithmetic, ZFC, or stronger theories?” The parenthetical is not a precise general definition: ordinal analysis commonly measures the well-orderings a theory can prove well-founded, and formulations of proof-theoretic ordinal vary. In one standard formulation, for a theory T⊇ACA0T\supseteq\mathrm{ACA}_0, define

∣T∣=sup⁡{ot⁡(≺):≺ is a computable well-ordering of N and T⊢Wo(≺)}.|T|=\sup\{\operatorname{ot}(\prec):\prec\text{ is a computable well-ordering of }\mathbb{N}\text{ and }T\vdash\mathrm{Wo}(\prec)\}.

Here ot⁡(≺)\operatorname{ot}(\prec) is the order type and Wo(≺)\mathrm{Wo}(\prec) asserts that ≺\prec is well-founded. “Second-order arithmetic” can mean a particular subsystem or the full theory Z2\mathbf Z_2; the latter has set variables ranging over sets of natural numbers and full comprehension. The question therefore asks broadly about the ordinal measure for Z2\mathbf Z_2, ZFC, and stronger theories, without specifying a single theory or ordinal-analysis convention for all of them. (A different working definition uses a least ordinal segment whose well-foundedness, over a basic theory, suffices to prove consistency.) Arai, An ordinal analysis of ΠN-Collection (2023 preprint) Rathjen, The Art of Measuring the Strength of Theories (2023)

Background

Ordinal analysis grew out of Hilbert’s program to establish consistency by finitary means. Gentzen’s 1936–38 consistency proofs for Peano arithmetic assigned ordinals to proofs and used reductions that lower those ordinals; the relevant boundary is ε0\varepsilon_0, the least positive fixed point of α↦ωα\alpha\mapsto\omega^\alpha. The method turned ordinals into measures of formal strength: besides consistency arguments, ordinal analyses can characterize provably recursive functions and yield conservation and independence results. The ordinal depends on an effective notation system and on the chosen measure, so “the smallest ordinal a theory cannot prove well-founded” is best treated as an informal gloss rather than a definition that applies uniformly to every theory. Rathjen, The Art of Measuring the Strength of Theories (2023) Rathjen, The art of ordinal analysis (2007)

The full second-order theory Z2\mathbf Z_2 allows quantification over sets of natural numbers and comprehension for every formula of its language; subsystems restrict which comprehension and other axioms are available. Proof theory first developed ordinal analyses for such subsystems, whose strengths can be expressed using increasingly powerful ordinal notation systems and collapsing functions. Rathjen’s 2023 survey described analyses reaching subsystems with Π21\Pi^1_2 comprehension and identified Π31\Pi^1_3 comprehension as a major barrier on the way to full Z2\mathbf Z_2. That dated account predates Arai’s later preprint claim about full Z2\mathbf Z_2. Rathjen, The Art of Measuring the Strength of Theories (2023) Rathjen, Recent Advances in Ordinal Analysis: Π¹₂-CA and Related Systems (1995)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.