Cohesive sets and rainbows

Abstract

We study the strength of $\RRT^3_2$, Rainbow Ramsey Theorem for colorings of triples, and prove that $\RCA + \RRT^3_2$ implies neither $\WKL$ nor $\RRT^4_2$. To this end, we establish some recursion theoretic properties of cohesive sets and rainbows for colorings of pairs. We show that every sequence (2-bounded coloring of pairs) admits a cohesive set (infinite rainbow) of non-PA Turing degree; and that every ${\varnothing }^{\prime }$-recursive sequence (2-bounded coloring of pairs) admits a $\low_3$ cohesive set (infinite rainbow).

References in corpus (1)

• Rainbow Ramsey theorem for triples is strictly weaker than the Arithmetic Comprehension Axiom

Cited by in corpus (5)

• Some logically weak Ramseyan theorems
• The Definability Strength of Combinatorial Principles
• Somewhere over the rainbow Ramsey theorem for pairs
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• SRT22 does not imply RT22 in omega-models