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

• Patey, Ludovic

• Yokoyama, Keita

Abstract

Ramsey's theorem for n-tuples and k-colors (RT^n_k) 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 Pi^0_1 consequences, and show that RT^2_2 is Pi^0_3 conservative over ISigma^0_1. This strengthens the proof of Chong, Slaman and Yang that RT^2_2 does not imply ISigma^0_2, and shows that 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.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/16703

Journal

• Advances in Mathematics

  Advances in Mathematics 330 1034-1070, 2018-07-21

  Elsevier

Keywords

• Reverse Mathematics
• Ramsey’s theorem
• proof-theoretic strength

Details

• CRID: 1050566774843915520
• NII Article ID: 120006874931
• ISSN: 00018708
• Web Site: http://hdl.handle.net/10119/16703
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • CiNii Articles