The Strength of the Rainbow Ramsey Theorem

Journal of Symbolic Logic 74 (4):1310 - 1324 (2009)

Abstract
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
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1254748693
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 46,206
Through your library

References found in this work BETA

Calibrating Randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
Computability Theory.Barry Cooper - 2010 - Journal of the Indian Council of Philosophical Research 27 (1).

Add more references

Citations of this work BETA

Cohesive Sets and Rainbows.Wei Wang - 2014 - Annals of Pure and Applied Logic 165 (2):389-408.
Degrees Bounding Principles and Universal Instances in Reverse Mathematics.Ludovic Patey - 2015 - Annals of Pure and Applied Logic 166 (11):1165-1185.

View all 7 citations / Add more citations

Similar books and articles

Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
Ramsey's Theorem and Cone Avoidance.Damir Dzhafarov & Carl Jockusch Jr - 2009 - Journal of Symbolic Logic 74 (2):557 - 578.
On the Ramsey Property for Sets of Reals.Ilias G. Kastanas - 1983 - Journal of Symbolic Logic 48 (4):1035-1045.
A Simple Proof and Some Difficult Examples for Hindman's Theorem.Henry Towsner - 2012 - Notre Dame Journal of Formal Logic 53 (1):53-65.
Ramsey's Representation Theorem.Richard Bradley - 2004 - Dialectica 58 (4):483–497.
Reverse Mathematics and a Ramsey-Type König's Lemma.Stephen Flood - 2012 - Journal of Symbolic Logic 77 (4):1272-1280.

Analytics

Added to PP index
2013-09-30

Total views
33 ( #276,305 of 2,285,685 )

Recent downloads (6 months)
7 ( #158,444 of 2,285,685 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature