The proof-theoretic strength of Ramsey's theorem for pairs and two colors.
The proof-theoretic strength of Ramsey's theorem for pairs and two colors.
复制标题
DOI：
10.1016/j.aim.2018.03.035
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
Ludovic Patey;K. Yokoyama
中科院分区：
文献类型：
--
作者：
Ludovic Patey;K. Yokoyama
Ramsey的n-元组和k-色定理（RT k n）断言[N] n的每一个k-着色都有一个无限单色子集。我们研究了Ramsey定理的证明理论强度，即它的100个结论的集合，并证明了RT 2 2是100个3 0保守的I 100。这加强了Chong，Slaman和Yang关于RT 2 2不包含I 2 0的证明，并表明RT 2 2是有限可约的，在希尔伯特纲领的Simpson部分实现的意义下。此外，我们还开发了一些通用的工具来简化30-守恒定理的证明。
Ramsey's theorem for n-tuples and k-colors (RT k 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 RT 2 2 is Π 3 0 conservative over I Σ 1 0. This strengthens the proof of Chong, Slaman and Yang that RT 2 2 does not imply I Σ 2 0, 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 Π 3 0-conservation theorems.