Some logically weak Ramseyan theorems

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 Erdős, Hajnal and Rado: $\omega \to [\omega {]}_{c,\le d}^r$, which asserts that for every $f:[\omega {]}^r\to c$ there exists an infinite $H$ with $|f([H{]}^r)|\le d$. 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 ${\mathrm{ACA}}_0$ over ${\mathrm{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 ${\mathrm{ACA}}_0$ over ${\mathrm{RCA}}_0$.

19 pages; with changes according to the referees

References in corpus (1)

• Cohesive sets and rainbows

Cited by in corpus (11)

• The Definability Strength of Combinatorial Principles
• Somewhere over the rainbow Ramsey theorem for pairs
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• 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
• On the logical strengths of partial solutions to mathematical problems
• Relationships between computability-theoretic properties of problems
• Ramsey-like theorems for the Schreier barrier
• The reverse mathematics of the Thin set and Erdős-Moser theorems
• The combinatorial equivalence of a computability theoretic question