{
  "id": "1601.00050",
  "version": "v1",
  "published": "2016-01-01T04:50:58.000Z",
  "updated": "2016-01-01T04:50:58.000Z",
  "title": "The proof-theoretic strength of Ramsey's theorem for pairs and two colors",
  "authors": [
    "Ludovic Patey",
    "Keita Yokoyama"
  ],
  "comment": "29 pages",
  "categories": [
    "math.LO"
  ],
  "abstract": "Ramsey's theorem for $n$-tuples and $k$-colors ($\\mathsf{RT}^n_k$) asserts that every k-coloring of $[\\mathbb{N}]^n$ admits an infinite monochromatic subset. We study the proof-theoretic strength of Ramsey's theorem for pairs and two colors, namely, the set of its $\\Pi^0_1$ consequences, and show that $\\mathsf{RT}^2_2$ is $\\Pi^0_3$ conservative over $\\mathsf{I}\\Sigma^0_1$. This strengthens the proof of Chong, Slaman and Yang that $\\mathsf{RT}^2_2$ does not imply $\\mathsf{I}\\Sigma^0_2$, and shows that $\\mathsf{RT}^2_2$ is finitistically reducible, in the sense of Simpson's partial realization of Hilbert's Program. Moreover, we develop general tools to simplify the proofs of $\\Pi^0_3$-conservation theorems.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-01-01T04:50:58.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "ramseys theorem",
      "proof-theoretic strength",
      "simpsons partial realization",
      "infinite monochromatic subset",
      "conservation theorems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 29,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160100050P"
    }
  }
}