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

MaRDI QIDQ3530396zbMATH OpenFDO

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

Publication date 20 October 2008

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

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)

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$.

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

Cited in

(28)

• Some results concerning the \(\mathsf{SRT}_2^2\) vs. \(\mathsf{COH}\) problem
• Degrees bounding principles and universal instances in reverse mathematics
• The strength of Ramsey's theorem for pairs over trees. I: Weak König's lemma
• Stable Ramsey's theorem and measure
• The definability strength of combinatorial principles
• Relationships between computability-theoretic properties of problems
• On notions of computability-theoretic reduction between Π21 principles
• The strength of the rainbow Ramsey Theorem
• The polarized Ramsey's theorem
• In search of the first-order part of Ramsey's theorem for pairs
• Computing sets from all infinite subsets
• Pigeons do not jump high
• An inside/outside Ramsey theorem and recursion theory
• Cone avoiding closed sets
• Partial orders and immunity in reverse mathematics
• Some Questions in Computable Mathematics
• On the strength of Ramsey's theorem for pairs
• Strong reductions between combinatorial principles
• Ramsey-type graph coloring and diagonal non-computability
• The weakness of being cohesive, thin or free in reverse mathematics
• Nonstandard methods in Ramsey's theorem for pairs
• Dominating the Erdős-Moser theorem in reverse mathematics
• On the role of the collection principle for \(\Sigma ^0_2\)-formulas in second-order reverse mathematics
• scientific article; zbMATH DE number 7377981 (Why is no real title available?)
• The thin set theorem for pairs implies DNR
• On the uniform computational content of Ramsey's theorem
• \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
• Open questions about Ramsey-type statements in reverse mathematics

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)