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

zbMATH Open1167.03009arXiv1408.2897MaRDI QIDQ3530396FDOQ3530396

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

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 (28)

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