Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



A packed Ramsey's theorem and computability theory

Author: Stephen Flood
Journal: Trans. Amer. Math. Soc. 367 (2015), 4957-4982
MSC (2010): Primary 03D80
Published electronically: February 3, 2015
MathSciNet review: 3335406
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Ramsey's theorem states that each coloring has an infinite homogeneous set, but these sets can be arbitrarily spread out. Paul Erdős and Fred Galvin proved that for each coloring $ f$, there is an infinite set that is ``packed together'' which is given ``a small number'' of colors by $ f$.

We analyze the strength of this theorem from the perspective of computability theory and reverse mathematics. We show that this theorem is close in computational strength to the standard Ramsey's theorem by giving arithmetical upper and lower bounds for solutions to computable instances. In reverse mathematics, we show that that this packed Ramsey's theorem is equivalent to Ramsey's theorem for exponents $ n\neq 2$. When $ n=2$, we show that it implies Ramsey's theorem and that it does not imply $ \mathsf {ACA}_0$.

References [Enhancements On Off] (What's this?)

  • [1] Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman, On the strength of Ramsey's theorem for pairs, J. Symbolic Logic 66 (2001), no. 1, 1-55. MR 1825173 (2002c:03094),
  • [2] Peter A. Cholak, Carl G. Jockusch Jr., and Theodore A. Slaman, Corrigendum to: ``On the strength of Ramsey's theorem for pairs'' [MR1825173], J. Symbolic Logic 74 (2009), no. 4, 1438-1439. MR 2583829 (2010k:03055),
  • [3] Paul Erdős and Fred Galvin, Some Ramsey-type theorems, Discrete Math. 87 (1991), no. 3, 261-269. MR 1095471 (92b:05078),
  • [4] Paul Erdős, András Hajnal, Attila Máté, and Richard Rado, Combinatorial set theory: partition relations for cardinals, Studies in Logic and the Foundations of Mathematics, vol. 106, North-Holland Publishing Co., Amsterdam, 1984. MR 795592 (87g:04002)
  • [5] Stephen Flood, Paths, trees, and the computational strength of some Ramsey-type theorems, Thesis (Ph.D.)-University of Notre Dame, 2012, ProQuest LLC, Ann Arbor, MI.
  • [6] -, Reverse mathematics and a Ramsey-type König's lemma, J. Symbolic Logic 77 (2012), no. 4, 1272-1280. MR 3051625
  • [7] Denis R. Hirschfeldt and Richard A. Shore, Combinatorial principles weaker than Ramsey's theorem for pairs, J. Symbolic Logic 72 (2007), no. 1, 171-206. MR 2298478 (2007m:03115),
  • [8] Jeffry Lynn Hirst, Combinatorics in Subsystems of Second Order Arithmetic, Thesis (Ph.D.)-The Pennsylvania State University, 1987, ProQuest LLC, Ann Arbor, MI. MR 2635978
  • [9] Carl G. Jockusch Jr., Ramsey's theorem and recursion theory, J. Symbolic Logic 37 (1972), 268-280. MR 0376319 (51 #12495)
  • [10] Jiayi Liu, $ {\mathsf {RT}}^2_2$ does not imply $ {\mathsf {WKL}}_0$, J. Symbolic Logic 77 (2012), no. 2, 609-620. MR 2963024,
  • [11] Stephen G. Simpson, Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge, 2009. MR 2517689 (2010e:03073)
  • [12] Robert I. Soare, Recursively enumerable sets and degrees, A study of computable functions and computably generated sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. MR 882921 (88m:03003)
  • [13] Robert I. Soare, Computability theory and applications: The art of classical computability [CTA], Springer-Verlag, to appear.
  • [14] Wei Wang, personal communication, 2011.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03D80

Retrieve articles in all journals with MSC (2010): 03D80

Additional Information

Stephen Flood
Affiliation: Department of Mathematics, Pennsylvania State University, McAllister Building, University Park, Pennsylvania 16802
Address at time of publication: Department of Mathematics, University of Connecticut, Waterbury Campus, 99 East Main Street, Waterbury, Connecticut 06702

Keywords: Ramsey's theorem, computability theory, reverse mathematics
Received by editor(s): July 20, 2012
Received by editor(s) in revised form: February 8, 2013, and April 26, 2013
Published electronically: February 3, 2015
Additional Notes: The author was partially supported by EMSW21-RTG 0353748, 0739007, and 0838506.
Article copyright: © Copyright 2015 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society