The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs

zbMATH Open1167.03009arXiv1408.2897MaRDI QIDQ3530396FDOQ3530396

Bjørn Kjos-Hanssen, Theodore A. Slaman, Steffen Lempp, Carl G. jun. Jockusch, Denis R. Hirschfeldt

Publication date: 20 October 2008

Abstract: We study the reverse mathematics and computability-the-o-re-tic strength of (stable) Ramsey's Theorem for pairs and the related principles COH and DNR. We show that SRT${}_2^2$ implies DNR over RCA${}_0$ but COH does not, and answer a question of Mileti by showing that every computable stable $2$-coloring of pairs has an incomplete $Delt{a}_2^0$ infinite homogeneous set. We also give some extensions of the latter result, and relate it to potential approaches to showing that SRT${}_2^2$ does not imply RT${}_2^2$.

Full work available at URL: https://arxiv.org/abs/1408.2897

Recommendations

• On the strength of Ramsey's theorem for pairs
• Strong reductions between combinatorial principles
• scientific article; zbMATH DE number 7377981
• Cohesive avoidance and strong reductions
• Combinatorial principles weaker than Ramsey's Theorem for pairs

zbMATH Keywords

reverse mathematicscohesive setRamsey's theorem for pairsWeak König's Lemmacomputable stable 2-coloring of pairsdiagonally non-recursive functionsinfinite homogeneous set

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35)

Cited In (21)

• Computing sets from all infinite subsets
• On the strength of Ramsey's theorem for pairs
• Nonstandard methods in Ramsey's theorem for pairs
• The polarized Ramsey's theorem
• Some Questions in Computable Mathematics
• Partial Orders and Immunity in Reverse Mathematics
• In search of the first-order part of Ramsey's theorem for pairs
• Cone avoiding closed sets
• The strength of Ramsey’s theorem for pairs over trees: I. Weak König’s Lemma
• On notions of computability-theoretic reduction between Π21 principles
• Dominating the Erdős-Moser theorem in reverse mathematics
• OPEN QUESTIONS ABOUT RAMSEY-TYPE STATEMENTS IN REVERSE MATHEMATICS
• Title not available (Why is that?)
• Degrees bounding principles and universal instances in reverse mathematics
• \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
• ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM
• The strength of the rainbow Ramsey Theorem
• Pigeons do not jump high
• An inside/outside Ramsey theorem and recursion theory
• The thin set theorem for pairs implies DNR
• RELATIONSHIPS BETWEEN COMPUTABILITY-THEORETIC PROPERTIES OF PROBLEMS

This page was built for publication: The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3530396)