CONSERVATION OF RAMSEY'S THEOREM FOR PAIRS AND WELL-FOUNDEDNESS

被引：1

作者：

LE Houerou, Quentin ^{[1
]}

Patey, Ludovic levy ^{[2
]}

Yokoyama, Keita ^{[3
]}

机构：

[1] Univ Paris Est Creteil Val Demarne, Lab Algorithm Complex & Log, Creteil, France

[2] Univ Paris Cite, Inst Math Jussieu Paris Rive Gauche, Equipe Log, CNRS, Campus Grands Moulins, Paris, France

[3] Tohoku Univ, Math Inst, Sendai, Japan

来源：

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY | 2025年 / 378卷 / 03期

关键词：

COMBINATORIAL PRINCIPLES WEAKER; STRENGTH; RECURSION;

D O I：

10.1090/tran/9336

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this article, we prove that Ramsey's theorem for pairs and two colors is Pi 11-conservative over RCA0 + B Sigma 0 2 + WF (epsilon 0 ) and over RCA0 + B Sigma 0 Tcaron; 2 + n WF ( omega n omega ). These results improve theorems from Chong, Slaman and Yang [Adv. Math. 308 (2017), pp. 121-141] and Kolodziejczyk and Yokoyama [In search of the first-order part of Ramsey's theorem for pairs, Springer, Cham, 2021] and belong to a long line of research towards the characterization of the first-order part of Ramsey's theorem for pairs.

引用

页码：2157 / 2186

页数：30

共 33 条

[1]

Belanger DR, 2022, Arxiv, DOI arXiv:2212.13011

[2] The strength of infinitary Ramseyan principles can be accessed by their densities [J].

Bovykin, Andrey ;

Weiermann, Andreas .

ANNALS OF PURE AND APPLIED LOGIC, 2017, 168 (09) :1700-1709

[3] On the strength of Ramsey's theorem for pairs [J].

Cholak, PA ;

Jockusch, CG ;

Slaman, TA .

JOURNAL OF SYMBOLIC LOGIC, 2001, 66 (01) :1-55

[4] The inductive strength of Ramsey's Theorem for Pairs [J].

Chong, C. T. ;

Slaman, Theodore A. ;

Yang, Yue .

ADVANCES IN MATHEMATICS, 2017, 308 :121-141

[5] Π11-conservation of combinatorial principles weaker than Ramsey's theorem for pairs [J].

Chong, C. T. ;

Slaman, Theodore A. ;

Yang, Yue .

ADVANCES IN MATHEMATICS, 2012, 230 (03) :1060-1077

[6] THE DEGREE OF A SIGMA-N CUT [J].

CHONG, CT ;

MOURAD, KJ .

ANNALS OF PURE AND APPLIED LOGIC, 1990, 48 (03) :227-235

[7]

Dzhafarov Damir D., 2022, Theory and Applications of Computability, pc2022, DOI DOI 10.1007/978-3-031-11367-3

[8]

Eastaugh B, 2017, STUD LOGICA, V105, P873, DOI 10.1007/s11225-017-9740-1

[9]

Erdos P., 1964, Magyar Tud. Akad. Mat. Kutato Int. Kozl, V9, P125

[10]

Fernandes AM, 2017, P231

← 1 2 3 4 →