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

被引：14

作者：

Patey, Ludovic ^{[1
]}

Yokoyama, Keita ^{[2
]}

机构：

[1] Univ Claude Bernard Lyon 1, Inst Camille Jordan, 43 Blvd 11 Novembre 1918, F-69622 Villeurbanne, France

[2] Japan Adv Inst Sci & Technol, Sch Informat Sci, 1-1 Asahidai, Nomi, Ishikawa 9231292, Japan

来源：

ADVANCES IN MATHEMATICS | 2018年 / 330卷

关键词：

Reverse mathematics; Ramsey's theorem; Proof-theoretic strength; COMBINATORIAL PRINCIPLES WEAKER; RECURSION; BOUNDS;

D O I：

10.1016/j.aim.2018.03.035

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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 Pi(0)(1) consequences, and show that RT22 is Pi(0)(3) conservative over I Sigma(0)(1). This strengthens the proof of Chong, Slaman and Yang that RT22 does not imply I Sigma(0)(2), 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 Pi(0)(3)-conservation theorems. (C) 2018 Elsevier Inc. All rights reserved.

引用

页码：1034 / 1070

页数：37

共 18 条

[11] On the strength of Ramsey's theorem for trees
Chong, C. T.
Li, Wei
Wang, Wei
Yang, Yue
ADVANCES IN MATHEMATICS, 2020, 369
[12] In Search of the First-Order Part of Ramsey's Theorem for Pairs
Kolodziejczyk, Leszek Aleksander
Yokoyama, Keita
CONNECTING WITH COMPUTABILITY, 2021, 12813 : 297 - 307
[13] THE STRENGTH OF RAMSEY'S THEOREM FOR PAIRS OVER TREES: I. WEAK KONIG'S LEMMA
Chong, Chi Tat
Li, Wei
Liu, Lu
Yang, Yue
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2021, 374 (08) : 5545 - 5581
[14] THE STRENGTH OF RAMSEY'S THEOREM FOR COLORING RELATIVELY LARGE SETS
Carlucci, Lorenzo
Zdanowski, Konrad
JOURNAL OF SYMBOLIC LOGIC, 2014, 79 (01) : 89 - 102
[15] Computable Ramsey's theorem for pairs needs infinitely many Π20 sets
Igusa, Gregory
Towsner, Henry
ARCHIVE FOR MATHEMATICAL LOGIC, 2017, 56 (1-2) : 155 - 160
[16] Π11-conservation of combinatorial principles weaker than Ramsey's theorem for pairs
Chong, C. T.
Slaman, Theodore A.
Yang, Yue
ADVANCES IN MATHEMATICS, 2012, 230 (03) : 1060 - 1077
[17] On the deductive strength of the Erdos-Dushnik-Miller theorem and two order-theoretic principles
Tachtsis, Eleftherios
MONATSHEFTE FUR MATHEMATIK, 2024, 203 (03): : 677 - 693
[18] Computable Ramsey’s theorem for pairs needs infinitely many Π20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi ^0_2$$\end{document} sets
Gregory Igusa
Henry Towsner
Archive for Mathematical Logic, 2017, 56 (1-2) : 155 - 160

← 1 2 →