Some logically weak Ramseyan theorems

DOI10.1016/J.AIM.2014.05.003MaRDI QIDQ2453567zbMATH OpenOpenAlexFDO

Authors Wei Wang

Publication date 10 June 2014

Published in Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

reverse mathematicsRamsey's theoremrainbow Ramsey theoremthin setfree set

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35)

Abstract: We study four families of consequences of Ramsey's Theorem from the viewpoint of reverse mathematics. The first, which we call the Achromatic Ramsey Theorem, is from a partition relation introduced by ErdH{o}s, Hajnal and Rado: $omegao[omega{]}_{c,leqd}^r$, which asserts that for every $f:[omega{]}^{r}oc$ there exists an infinite $H$ with $|f([H{]}^r)|leqd$. The second and third are the Free Set Theorem and the Thin Set Theorem, which were introduced by Harvey Friedman. And the last is the Rainbow Ramsey Theorem. We show that, most theorems from these families are quite weak, i.e., they are strictly weaker than $operatorname{ACA}_0$ over $operatorname{RCA}_0$. Interestingly, these families turn out to be closely related. We establish the so-called strong cone avoidance property of most instances of the Achromatic Ramsey Theorem by an induction of exponents, then apply this and a similar induction to obtain the strong cone avoidance property of the Free Set Theorem. From the strong cone avoidance property of the Achromatic Ramsey Theorem and the Free Set Theorem, we derive the strong cone property of the Thin Set Theorem and the Rainbow Ramsey Theorem. It follws easily that a theorem with the strong cone avoidance property does not imply $operatorname{ACA}_0$ over $operatorname{RCA}_0$.

Recommendations

• Effective versions of Ramsey's Theorem: Avoiding the cone above 0′
• The strength of the rainbow Ramsey Theorem
• An analysis of Ramsey's theorem
• The weakness of being cohesive, thin or free in reverse mathematics
• On the strength of Ramsey's theorem

Cites work

• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 1226875 (Why is no real title available?)
• scientific article; zbMATH DE number 2236628 (Why is no real title available?)
• Cohesive sets and rainbows
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• On the strength of Ramsey's theorem
• On the strength of Ramsey's theorem for pairs
• Partition relations for cardinal numbers
• Rainbow Ramsey theorem for triples is strictly weaker than the arithmetical comprehension axiom
• Ramsey's theorem and cone avoidance
• Ramsey's theorem and recursion theory
• Reverse mathematics, computability, and partitions of trees
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• The strength of the rainbow Ramsey Theorem
• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(25)

• On the logical strengths of partial solutions to mathematical problems
• The definability strength of combinatorial principles
• Relationships between computability-theoretic properties of problems
• scientific article; zbMATH DE number 4029558 (Why is no real title available?)
• Comparisons of polychromatic and monochromatic Ramsey theory
• On the strength of Ramsey's theorem without \(\Sigma _{1}\)-induction
• On uniform relationships between combinatorial problems
• Controlling iterated jumps of solutions to combinatorial problems
• Thin set theorems and cone avoidance
• Ramsey's theorem and cone avoidance
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• Rainbow Ramsey theorem for triples is strictly weaker than the arithmetical comprehension axiom
• Degrees bounding principles and universal instances in reverse mathematics
• Iterative forcing and hyperimmunity in reverse mathematics
• Ramsey-like theorems and moduli of computation
• Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective
• Pigeons do not jump high
• Thin set versions of Hindman's theorem
• Constructing sequences one step at a time
• The weakness of being cohesive, thin or free in reverse mathematics
• The thin set theorem for pairs implies DNR
• On the strength of Ramsey's theorem for trees
• Open questions about Ramsey-type statements in reverse mathematics
• THE REVERSE MATHEMATICS OF THE THIN SET AND ERDŐS–MOSER THEOREMS
• scientific article; zbMATH DE number 2236628 (Why is no real title available?)

This page was built for publication: Some logically weak Ramseyan theorems

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