Some logically weak Ramseyan theorems

DOI10.1016/J.AIM.2014.05.003zbMATH Open1307.03011arXiv1303.3331OpenAlexW2111379744MaRDI QIDQ2453567FDOQ2453567

Authors: Wei Wang 

Publication date: 10 June 2014

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

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

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• Comparisons of polychromatic and monochromatic Ramsey theory
• On the strength of Ramsey's theorem without \(\Sigma _{1}\)-induction
• On uniform relationships between combinatorial problems
• Thin set theorems and cone avoidance
• Controlling iterated jumps of solutions to combinatorial problems
• 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
• Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective
• Ramsey-like theorems and moduli of computation
• 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
• Open questions about Ramsey-type statements in reverse mathematics
• On the strength of Ramsey's theorem for trees
• THE REVERSE MATHEMATICS OF THE THIN SET AND ERDŐS–MOSER THEOREMS
• Title not available (Why is that?)

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)