Dickson's lemma and weak Ramsey theory

被引：0

作者：

Omata, Yasuhiko ^{[1
]}

Pelupessy, Florian ^{[1
]}

机构：

[1] Tohoku Univ, Math Inst, Aoba Ku, 6-3 Aramaki Aza Aoba, Sendai, Miyagi 9808578, Japan

来源：

ARCHIVE FOR MATHEMATICAL LOGIC | 2019年 / 58卷 / 3-4期

关键词：

Reverse mathematics; Ramsey theory; Dickson's lemma;

D O I：

10.1007/s00153-018-0642-3

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We explore the connections between Dickson's lemma and weak Ramsey theory. We show that a weak version of the Paris-Harrington principle for pairs in c colors and miniaturized Dickson's lemma for c-tuples are equivalent over RCA(0)*. Furthermore, we look at a cascade of consequences for several variants of weak Ramsey's theorem.

引用

页码：413 / 425

页数：13

共 16 条

[1]

[Anonymous], PERSPECTIVES LOGIC

[2] Sharp thresholds for hypergraph regressive Ramsey numbers [J].

Carlucci, Lorenzo ;

Lee, Gyesik ;

Weiermann, Andreas .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 2011, 118 (02) :558-585

[3] SOME BOUNDS FOR THE RAMSEY-PARIS-HARRINGTON NUMBERS [J].

ERDOS, P ;

MILLS, G .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1981, 30 (01) :53-70

[4] Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma [J].

Figueira, Diego ;

Figueira, Santiago ;

Schmitz, Sylvain ;

Schnoebelen, Philippe .

26TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2011), 2011, :269-278

[5]

Friedman H. M., 2010, ADJACENT RAMSE UNPUB

[6] INDEPENDENCE OF RAMSEY THEOREM VARIANTS USING ε0 [J].

Friedman, Harvey ;

Pelupessy, Florian .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2016, 144 (02) :853-860

[7]

Gordan PA, 1899, NACHR GES WISS GO MP, V1899, P240

[8] Phase transitions of iterated Higman-style well-partial-orderings [J].

Gordeev, Lev ;

Weiermann, Andreas .

ARCHIVE FOR MATHEMATICAL LOGIC, 2012, 51 (1-2) :127-161

[9]

Hajek P., 1998, METAMATHEMATICS 1 OR

[10] RAPIDLY GROWING RAMSEY FUNCTIONS [J].

KETONEN, J ;

SOLOVAY, R .

ANNALS OF MATHEMATICS, 1981, 113 (02) :267-314

← 1 2 →