The proof-theoretic strength of Ramsey's theorem for pairs and two colors

Ludovic Patey, Keita Yokoyama

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)

Abstract

Ramsey's theorem for n-tuples and k-colors (RTk n) asserts that every k-coloring of [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 Π1 0 consequences, and show that RT2 2 is Π3 0 conservative over IΣ1 0. This strengthens the proof of Chong, Slaman and Yang that RT2 2 does not imply IΣ2 0, and shows that RT2 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 Π3 0-conservation theorems.

Original languageEnglish
Pages (from-to)1034-1070
Number of pages37
JournalAdvances in Mathematics
Volume330
DOIs
Publication statusPublished - 2018 May 25

Keywords

  • Proof-theoretic strength
  • Ramsey's theorem
  • Reverse mathematics

Fingerprint

Dive into the research topics of 'The proof-theoretic strength of Ramsey's theorem for pairs and two colors'. Together they form a unique fingerprint.

Cite this