Journal of Symbolic Logic 76 (2):575 - 602 (2011)

We study the computability-theoretic complexity and proof-theoretic strength of the following statements: (1) "If X is a well-ordering, then so is ε X ", and (2) "If X is a well-ordering, then so is φ(α, X)", where α is a fixed computable ordinal and φ represents the two-placed Veblen function. For the former statement, we show that ω iterations of the Turing jump are necessary in the proof and that the statement is equivalent to ${\mathrm{A}\mathrm{C}\mathrm{A}}_{0}^{+}$ over RCA₀. To prove the latter statement we need to use ω α iterations of the Turing jump, and we show that the statement is equivalent to ${\mathrm{\Pi }}_{{\mathrm{\omega }}^{\mathrm{\alpha }}}^{0}{-\mathrm{C}\mathrm{A}}_{0}$ . Our proofs are purely computability-theoretic. We also give a new proof of a result of Friedman: the statement "if x is a well-ordering, then so is φ(x, 0)" is equivalent to ATR₀ over RCA₀
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1305810765
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 51,447
Through your library

References found in this work BETA

Proof Theory and Logical Complexity.Helmut Pfeifer & Jean-Yves Girard - 1989 - Journal of Symbolic Logic 54 (4):1493.
Reverse Mathematics and Ordinal Exponentiation.Jeffry L. Hirst - 1994 - Annals of Pure and Applied Logic 66 (1):1-18.

Add more references

Citations of this work BETA

Derivatives of Normal Functions and $$\Omega $$ Ω -Models.Toshiyasu Arai - 2018 - Archive for Mathematical Logic 57 (5-6):649-664.
Reverse Mathematics: The Playground of Logic.Richard A. Shore - 2010 - Bulletin of Symbolic Logic 16 (3):378-402.
From Hierarchies to Well-Foundedness.Dandolo Flumini & Kentaro Sato - 2014 - Archive for Mathematical Logic 53 (7-8):855-863.
Proof-Theoretic Strengths of the Well-Ordering Principles.Toshiyasu Arai - 2020 - Archive for Mathematical Logic 59 (3-4):257-275.
Computable Aspects of the Bachmann–Howard Principle.Anton Freund - 2019 - Journal of Mathematical Logic 20 (2):2050006.

Add more citations

Similar books and articles

Determinacy in Strong Cardinal Models.P. D. Welch - 2011 - Journal of Symbolic Logic 76 (2):719 - 728.
Necessary Use of [Image] Induction in a Reversal.Itay Neeman - 2011 - Journal of Symbolic Logic 76 (2):561 - 574.
A Hierarchy of Tree-Automatic Structures.Olivier Finkel & Stevo Todorčević - 2012 - Journal of Symbolic Logic 77 (1):350-368.
On the Jump Classes of Noncuppable Enumeration Degrees.Charles M. Harris - 2011 - Journal of Symbolic Logic 76 (1):177 - 197.
Consecutive Singular Cardinals and the Continuum Function.Arthur W. Apter & Brent Cody - 2013 - Notre Dame Journal of Formal Logic 54 (2):125-136.
Elementary Cuts in Saturated Models of Peano Arithmetic.James H. Schmerl - 2012 - Notre Dame Journal of Formal Logic 53 (1):1-13.


Added to PP index

Total views
9 ( #852,294 of 2,330,441 )

Recent downloads (6 months)
1 ( #584,494 of 2,330,441 )

How can I increase my downloads?


My notes