The canonical Ramsey theorem and computability theory
HTML articles powered by AMS MathViewer
- by Joseph R. Mileti PDF
- Trans. Amer. Math. Soc. 360 (2008), 1309-1340 Request permission
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
- Peter A. Cholak, Mariagnese Giusto, Jeffry L. Hirst, and Carl G. Jockusch Jr., Free sets and reverse mathematics, Reverse mathematics 2001, Lect. Notes Log., vol. 21, Assoc. Symbol. Logic, La Jolla, CA, 2005, pp. 104–119. MR 2185429
- 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
- P. Erdös and R. Rado, A combinatorial theorem, J. London Math. Soc. 25 (1950), 249–255. MR 37886, DOI 10.1112/jlms/s1-25.4.249
- Petr Hájek and Pavel Pudlák, Metamathematics of first-order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1993. MR 1219738, DOI 10.1007/978-3-662-22156-3
- Jeffry L. Hirst, Combinatorics in subsystems of second order arithmetic, Ph.D. thesis, The Pennsylvania State University, 1987.
- 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, DOI 10.2307/2695050
- Carl Jockusch and Frank Stephan, A cohesive set which is not high, Math. Logic Quart. 39 (1993), no. 4, 515–530. MR 1270396, DOI 10.1002/malq.19930390153
- Carl Jockusch and Frank Stephan, Correction to: “A cohesive set which is not high” [Math. Logic Quart. 39 (1993), no. 4, 515–530; MR1270396 (95d:03078)], Math. Logic Quart. 43 (1997), no. 4, 569. MR 1477624, DOI 10.1002/malq.19970430412
- Carl G. Jockusch Jr., Ramsey’s theorem and recursion theory, J. Symbolic Logic 37 (1972), 268–280. MR 376319, DOI 10.2307/2272972
- 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 316227, DOI 10.1090/S0002-9947-1972-0316227-0
- Akihiro Kanamori, The higher infinite, 2nd ed., Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. Large cardinals in set theory from their beginnings. MR 1994835
- Akihiro Kanamori and Kenneth McAloon, On Gödel incompleteness and finite combinatorics, Ann. Pure Appl. Logic 33 (1987), no. 1, 23–41. MR 870685, DOI 10.1016/0168-0072(87)90074-1
- Joseph R. Mileti, Ramsey degrees, to appear.
- Handbook of mathematical logic, Studies in Logic and the Foundations of Mathematics, vol. 90, North-Holland Publishing Co., Amsterdam, 1977. With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis and A. S. Troelstra. MR 457132
- Richard Rado, Note on canonical partitions, Bull. London Math. Soc. 18 (1986), no. 2, 123–126. MR 818813, DOI 10.1112/blms/18.2.123
- F. P. Ramsey, On a problem in formal logic, Proc. London Math. Soc. (3) 30 (1930), 264–286.
- 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
- 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, DOI 10.1305/ndjfl/1040136917
- Handbook of mathematical logic, Studies in Logic and the Foundations of Mathematics, vol. 90, North-Holland Publishing Co., Amsterdam, 1977. With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis and A. S. Troelstra. MR 457132
- Stephen G. Simpson, Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. MR 1723993, DOI 10.1007/978-3-642-59971-2
- 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
- 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
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
- 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.
- © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2357697