The veblen functions for computability theorists

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

Abstract

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₀

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,990

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2013-09-30

Downloads
39 (#398,421)

6 months
26 (#139,639)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Computable aspects of the Bachmann–Howard principle.Anton Freund - 2019 - Journal of Mathematical Logic 20 (2):2050006.
From hierarchies to well-foundedness.Dandolo Flumini & Kentaro Sato - 2014 - Archive for Mathematical Logic 53 (7-8):855-863.
Derivatives of normal functions in reverse mathematics.Anton Freund & Michael Rathjen - 2021 - Annals of Pure and Applied Logic 172 (2):102890.
Reverse mathematics: the playground of logic.Richard A. Shore - 2010 - Bulletin of Symbolic Logic 16 (3):378-402.
Derivatives of normal functions and $$\omega $$ ω -models.Toshiyasu Arai - 2018 - Archive for Mathematical Logic 57 (5-6):649-664.

View all 10 citations / Add more citations

References found in this work

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