A model is computable if its domain is a computable set and its relations and functions are uniformly computable. Let be a computable model and let R be an extra relation on the domain of . That is, R is not named in the language of . We define to be the set of Turing degrees of the images f under all isomorphisms f from to computable models. We investigate conditions on and R which are sufficient and necessary for to (...) contain every Turing degree. These conditions imply that if every Turing degree 0″ can be realized in via an isomorphism of the same Turing degree as its image of R, then contains every Turing degree. We also discuss an example of and R whose coincides with the Turing degrees which are 0′. (shrink)

We study the strength of RRT32, Rainbow Ramsey Theorem for colorings of triples, and prove that RCA0 + RRT32 implies neither WKL0 nor RRT42 source. To this end, we establish some recursion theoretic properties of cohesive sets and rainbows for colorings of pairs. We show that every sequence admits a cohesive set of non-PA Turing degree; and that every ∅′-recursive sequence admits a low3 cohesive set.

In recent years, there has been a substantial amount of work in reverse mathematics concerning natural mathematical principles that are provable from RT, Ramsey's Theorem for Pairs. These principles tend to fall outside of the "big five" systems of reverse mathematics and a complicated picture of subsystems below RT has emerged. In this paper, we answer two open questions concerning these subsystems, specifically that ADS is not equivalent to CAC and that EM is not equivalent to RT.