The Rainbow Ramsey Theorem is essentially an "anti-Ramsey" theorem which states that certain types of colorings must be injective on a large subset (rather than constant on a large subset). Surprisingly, this version follows easily from Ramsey's Theorem, even in the weak system RCA₀ of reverse mathematics. We answer the question of the converse implication for pairs, showing that the Rainbow Ramsey Theorem for pairs is in fact strictly weaker than Ramsey's Theorem for pairs over RCA₀. The separation involves techniques (...) from the theory of randomness by showing that every 2-random bounds an ω-model of the Rainbow Ramsey Theorem for pairs. These results also provide as a corollary a new proof of Martin's theorem that the hyperimmune degrees have measure one. (shrink)

The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n ∈ ω (...) with its set of predecessors, so n = {0, 1, 2, …, n − 1}. (shrink)

We show, relative to the base theory RCA₀: A nontrivial tree satisfies Ramsey's Theorem only if it is biembeddable with the complete binary tree. There is a class of partial orderings for which Ramsey's Theorem for pairs is equivalent to ACA₀. Ramsey's Theorem for singletons for the complete binary tree is stronger than $B\sum_{2}^{0}$ , hence stronger than Ramsey's Theorem for singletons for ω. These results lead to extensions of results, or answers to questions, of Chubb, Hirst, and McNicholl [3].

In many simple integral domains, such as Z or Z[i], there is a straightforward procedure to determine if an element is prime by simply reducing to a direct check of finitely many potential divisors. Despite the fact that such a naive approach does not immediately translate to integral domains like Z[x] or the ring of integers in an algebraic number field, there still exist computational procedures that work to determine the prime elements in these cases. In contrast, we will show (...) how to computably extend Z in such a way that we can control the ordinary integer primes in any Π20 way, all while maintaining unique factorization. As a corollary, we establish the existence of a computable unique factorization domain such that the set of primes is Π20-complete in every computable presentation. (shrink)