Transactions of the American Mathematical Society

Author(s): Joseph R. Mileti
Journal: Trans. Amer. Math. Soc. 360 (2008), 1309-1340.
MSC (2000): Primary 03D80, 05D10
Posted: October 23, 2007
Retrieve article in: PDF DVI PostScript

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.

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)

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

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: 10.1090/S0002-9947-07-04390-5
PII: S 0002-9947(07)04390-5
Keywords: Computability theory, Ramsey theory, recursion theory, reverse mathematics
Received by editor(s): August 29, 2005
Posted: 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 of article: Copyright 2007, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS