Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-28T19:57:31.212Z Has data issue: false hasContentIssue false
  • English
  • Français

The strength of the rainbow Ramsey Theorem

Published online by Cambridge University Press:  12 March 2014

Barbara F. Csima  and
Joseph R. Mileti
Barbara F. Csima
Affiliation:
Department of Pure Mathematics, University of Waterloo, Waterloo, On, N2L 3G1, Canada, URL: www.math.uwaterloo.ca/~csima, E-mail: [email protected]
Joseph R. Mileti
Affiliation:
Department of Mathematics and Statistics, Grinnell College, Grinnel, Ia 50112-1690, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 RCA0 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 RCA0. 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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 74 , Issue 4 , December 2009 , pp. 1310 - 1324
Copyright
Copyright © Association for Symbolic Logic 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Abraham, Uri, Cummings, James, and Smyth, Clifford, Some results in polychromatic Ramsey theory, this Journal, vol. 72 (2007), no. 3, pp. 865–896.Google Scholar
[2]Alspach, Brian, Gerson, Martin, Hahn, Geňa, and Hell, Pavol, On sub-Ramsey numbers, Ars Combinatoria, vol. 22 (1986), pp. 199–206.Google Scholar
[3]Cholak, Peter A., Jockusch, Carl G., and Slaman, Theodore A., On the strength of Ramsey's theorem for pairs, this Journal, vol. 66 (2001), no. 1, pp. 1–55.Google Scholar
[4]Cooper, S. Barry, Computability theory, Chapman & Hall/CRC, Boca Raton, FL, 2004.Google Scholar
[5]Downey, Rod and Hirschfeldt, Denis R., Algorithmic randomness and complexity, Springer-Verlag, to appear.Google Scholar
[6]Downey, Rod, Hirschfeldt, Denis R., Nies, André, and Terwijn, Sebastiaan A., Calibrating randomness, The Bulletin of Symbolic Logic, vol. 12 (2006), no. 3, pp. 411–491.CrossRefGoogle Scholar
[7]Hell, Pavol and Montellano-Ballesteros, Juan José, Polychromatic cliques, Discrete Mathematics, vol. 285 (2004), no. 1-3, pp. 319–322.CrossRefGoogle Scholar
[8]Hirschfeldt, Denis R. and Shore, Richard A., Combinatorial principles weaker than Ramsey's theorem for pairs, this Journal, vol. 72 (2007), no. 1, pp. 171–206.Google Scholar
[9]Jockusch, Carl G. Jr., Ramsey's theorem and recursion theory, this Journal, vol. 37 (1972), pp. 268–280.Google Scholar
[10]Jockusch, Carlg. Jr. and Soare, Robert I., Π10 classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[11]Kučera, Antonín, Measure, Σ10-classes and complete extensions of PA, Recursion theory week (Oberwolfach, 1984), Lecture Notes in Math., vol. 1141, Springer, Berlin, 1985, pp. 245–259.CrossRefGoogle Scholar
[12]Mileti, Joseph R., Partition theorems and computability theory, Ph.D. thesis, University of Illinois at Urbana-Champaign, 2004.Google Scholar
[13]Mileti, Joseph R., The canonical Ramsey theorem and computability theory, Transactions of the American Mathematical Society, vol. 360 (2008), no. 3, pp. 1309–1340 (electronic).CrossRefGoogle Scholar
[14]Nies, Andre, Computability and randomness, Oxford University Press, New York, 2009.CrossRefGoogle Scholar
[15]Seetapun, David and Slaman, Theodore A., On the strength of Ramsey's theorem, Notre Dame Journal of Formal Logic, vol. 36 (1995), no. 4, pp. 570–582, Special Issue: Models of arithmetic.CrossRefGoogle Scholar
[16]Simpson, Stephen G., Subsystems of secondorder arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999.CrossRefGoogle Scholar
[17]Soare, Robert I., Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987, A study of computable functions and computably generated sets.CrossRefGoogle Scholar
[18]Todorčević, Stevo, Forcing positive partition relations, Transactions of the American Mathematical Society, vol. 280 (1983), no. 2, pp. 703–720.CrossRefGoogle Scholar
[19]van Lambalgen, Michiel, Random sequences, Ph.D. thesis, University of Amsterdam, 1987.Google Scholar