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…
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 , define
Here is the order type and asserts that is well-founded. “Second-order arithmetic” can mean a particular subsystem or the full theory ; the latter has set variables ranging over sets of natural numbers and full comprehension. The question therefore asks broadly about the ordinal measure for , 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 , the least positive fixed point of . 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 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 comprehension and identified comprehension as a major barrier on the way to full . That dated account predates Arai’s later preprint claim about full . Rathjen, The Art of Measuring the Strength of Theories (2023) Rathjen, Recent Advances in Ordinal Analysis: Π¹₂-CA and Related Systems (1995)
References
Progress summary
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.