A packed Ramsey’s theorem and computability theory
HTML articles powered by AMS MathViewer
- by Stephen Flood PDF
- Trans. Amer. Math. Soc. 367 (2015), 4957-4982 Request permission
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
- 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, DOI 10.2307/2694910
- 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, DOI 10.2178/jsl/1254748700
- Paul Erdős and Fred Galvin, Some Ramsey-type theorems, Discrete Math. 87 (1991), no. 3, 261–269. MR 1095471, DOI 10.1016/0012-365X(91)90135-O
- 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
- 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.
- Stephen Flood, Reverse mathematics and a Ramsey-type König’s lemma, J. Symbolic Logic 77 (2012), no. 4, 1272–1280. MR 3051625, DOI 10.2178/jsl.7704120
- 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, DOI 10.2178/jsl/1174668391
- Jeffry Lynn Hirst, COMBINATORICS IN SUBSYSTEMS OF SECOND ORDER ARITHMETIC, ProQuest LLC, Ann Arbor, MI, 1987. Thesis (Ph.D.)–The Pennsylvania State University. MR 2635978
- Carl G. Jockusch Jr., Ramsey’s theorem and recursion theory, J. Symbolic Logic 37 (1972), 268–280. MR 376319, DOI 10.2307/2272972
- Jiayi Liu, ${\mathsf {RT}}^2_2$ does not imply ${\mathsf {WKL}}_0$, J. Symbolic Logic 77 (2012), no. 2, 609–620. MR 2963024, DOI 10.2178/jsl/1333566640
- Stephen G. Simpson, Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR 2517689, DOI 10.1017/CBO9780511581007
- Robert I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR 882921, DOI 10.1007/978-3-662-02460-7
- Robert I. Soare, Computability theory and applications: The art of classical computability [CTA], Springer-Verlag, to appear.
- Wei Wang, personal communication, 2011.
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
- Email: sflood@alumni.nd.edu
- 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.
- © Copyright 2015
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 367 (2015), 4957-4982
- MSC (2010): Primary 03D80
- DOI: https://doi.org/10.1090/S0002-9947-2015-06164-9
- MathSciNet review: 3335406