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)

 
 

 

The canonical Ramsey theorem and computability theory


Author: Joseph R. Mileti
Journal: Trans. Amer. Math. Soc. 360 (2008), 1309-1340
MSC (2000): Primary 03D80, 05D10
DOI: https://doi.org/10.1090/S0002-9947-07-04390-5
Published electronically: October 23, 2007
MathSciNet review: 2357697
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Using the tools of computability theory and reverse mathematics, we study the complexity of two partition theorems, the Canonical Ramsey Theorem of Erdös and Rado, and the Regressive Function Theorem of Kanamori and McAloon. Our main aim is to analyze the complexity of the solutions to computable instances of these problems in terms of the Turing degrees and the arithmetical hierarchy. We succeed in giving a sharp characterization for the Canonical Ramsey Theorem for exponent 2 and for the Regressive Function Theorem for all exponents. These results rely heavily on a new, purely inductive, proof of the Canonical Ramsey Theorem. This study also unearths some interesting relationships between these two partition theorems, Ramsey's Theorem, and König's Lemma.


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

  • 1. Peter Cholak, Mariagnese Guisto, Jeffry Hirst, and Carl Jockusch, Jr., Free sets and reverse mathematics, Reverse Mathematics 2001 (Stephen G. Simpson, ed.), Lect. Notes Log. 21, Assoc. Symbol. Logic, La Jolla, CA, 2005. MR 2185429 (2006g:03101)
  • 2. 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)
  • 3. P. Erdös and R. Rado, A combinatorial theorem, J. London Math. Soc. 25 (1950), 249-255. MR 0037886 (12:322f)
  • 4. Petr Hájek and Pavel Pudlák, Metamathematics of first-order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1993. MR 1219738 (94d:03001)
  • 5. Jeffry L. Hirst, Combinatorics in subsystems of second order arithmetic, Ph.D. thesis, The Pennsylvania State University, 1987.
  • 6. Tamara J. Hummel and Carl G. Jockusch, Jr., Ramsey's theorem for computably enumerable colorings, J. Symbolic Logic 66 (2001), no. 2, 873-880. MR 1833484 (2002f:03077)
  • 7. Carl Jockusch and Frank Stephan, A cohesive set which is not high, Math. Logic Quart. 39 (1993), no. 4, 515-530. MR 1270396 (95d:03078)
  • 8. -, Correction to: ``A cohesive set which is not high'' [Math. Logic Quart. 39 (1993), no. 4, 515-530], Math. Logic Quart. 43 (1997), no. 4, 569. MR 1477624 (99a:03044)
  • 9. Carl G. Jockusch, Jr., Ramsey's theorem and recursion theory, J. Symbolic Logic 37 (1972), 268-280. MR 0376319 (51:12495)
  • 10. Carl G. Jockusch, Jr. and Robert I. Soare, $ \Pi^0_1$ classes and degrees of theories, Trans. Amer. Math. Soc. 173 (1972), 33-56. MR 0316227 (47:4775)
  • 11. Akihiro Kanamori, The higher infinite, second ed., Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003, Large cardinals in set theory from their beginnings. MR 1994835 (2004f:03092)
  • 12. Akihiro Kanamori and Kenneth McAloon, On Gödel incompleteness and finite combinatorics, Ann. Pure Appl. Logic 33 (1987), no. 1, 23-41. MR 870685 (88i:03095)
  • 13. Joseph R. Mileti, Ramsey degrees, to appear.
  • 14. J. Paris and Leo A. Harrington, A mathematical incompleteness in Peano arithmetic, Handbook of Mathematical Logic (Jon Barwise, ed.), North-Holland Publishing Co., Amsterdam, 1977, pp. 1133-1142. MR 0457132 (56:15351)
  • 15. Richard Rado, Note on canonical partitions, Bull. London Math. Soc. 18 (1986), no. 2, 123-126. MR 818813 (87e:05013)
  • 16. F. P. Ramsey, On a problem in formal logic, Proc. London Math. Soc. (3) 30 (1930), 264-286.
  • 17. Dana Scott, Algebras of sets binumerable in complete extensions of arithmetic, Proc. Sympos. Pure Math., Vol. V, American Mathematical Society, Providence, R.I., 1962, pp. 117-121. MR 0141595 (25:4993)
  • 18. David Seetapun and Theodore A. Slaman, On the strength of Ramsey's theorem, Notre Dame J. Formal Logic 36 (1995), no. 4, 570-582, Special Issue: Models of arithmetic. MR 1368468 (96k:03136)
  • 19. Stephen G. Simpson, Degrees of unsolvability: a survey of results, Handbook of Mathematical Logic (Jon Barwise, ed.), North-Holland, Amsterdam, 1977, pp. 1133-1142. MR 0457132 (56:15351)
  • 20. -, Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. MR 1723993 (2001i:03126)
  • 21. 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 (88m:03003)
  • 22. E. Specker, Ramsey's theorem does not hold in recursive set theory, Logic Colloquium '69 (Proc. Summer School and Colloq., Manchester, 1969), North-Holland, Amsterdam, 1971, pp. 439-442. MR 0278941 (43:4667)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03D80, 05D10

Retrieve articles in all journals with MSC (2000): 03D80, 05D10


Additional Information

Joseph R. Mileti
Affiliation: Department of Mathematics, University of Illinois, 1409 W. Green Street, Urbana, Illinois 61801
Address at time of publication: Department of Mathematics, University of Chicago, 5734 S. University Ave., Chicago, Illinois 60637
Email: mileti@math.uchicago.edu

DOI: https://doi.org/10.1090/S0002-9947-07-04390-5
Keywords: Computability theory, Ramsey theory, recursion theory, reverse mathematics
Received by editor(s): August 29, 2005
Published electronically: October 23, 2007
Additional Notes: Most of the results in this paper appear in the author’s dissertation written at the University of Illinois at Urbana-Champaign under the direction of Carl Jockusch with partial financial support provided by NSF Grant DMS-9983160.
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society