Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8904852 | Advances in Mathematics | 2018 | 37 Pages |
Abstract
Ramsey's theorem for n-tuples and k-colors (RTkn) 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 Π10 consequences, and show that RT22 is Π30 conservative over IΣ10. This strengthens the proof of Chong, Slaman and Yang that RT22 does not imply IΣ20, and shows that RT22 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 Π30-conservation theorems.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Mathematics (General)
Authors
Ludovic Patey, Keita Yokoyama,