{
  "id": "0910.5442",
  "version": "v2",
  "published": "2009-10-28T17:30:02.000Z",
  "updated": "2010-07-06T12:49:19.000Z",
  "title": "The Veblen functions for computability theorists",
  "authors": [
    "Alberto Marcone",
    "Antonio Montalbán"
  ],
  "comment": "26 pages, 3 figures, to appear in Journal of Symbolic Logic",
  "journal": "The Journal of Symbolic Logic 76 (2011), 575-602",
  "doi": "10.2178/jsl/1305810765",
  "categories": [
    "math.LO"
  ],
  "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 epsilon_X\", and (2) \"If X is a well-ordering, then so is phi(alpha,X)\", where alpha is a fixed computable ordinal and phi the two-placed Veblen function. For the former statement, we show that omega iterations of the Turing jump are necessary in the proof and that the statement is equivalent to ACA_0^+ over RCA_0. To prove the latter statement we need to use omega^alpha iterations of the Turing jump, and we show that the statement is equivalent to Pi^0_{omega^alpha}-CA_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 phi(X,0)\" is equivalent to ATR_0 over RCA_0.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-07-06T12:49:19.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03B30",
      "03D80",
      "03F15"
    ],
    "keywords": [
      "computability theorists",
      "turing jump",
      "equivalent",
      "proof-theoretic strength",
      "omega iterations"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0910.5442M"
    }
  }
}