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 Free Access

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.

- 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 https://doi.org/10.2307/2694910 - P. Erdös and R. Rado,
*A combinatorial theorem*, J. London Math. Soc.**25**(1950), 249–255. MR**37886**, DOI https://doi.org/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** - 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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1002/malq.19970430412 - Carl G. Jockusch Jr.,
*Ramsey’s theorem and recursion theory*, J. Symbolic Logic**37**(1972), 268–280. MR**376319**, DOI https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0168-0072%2887%2990074-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 https://doi.org/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 https://doi.org/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** - 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** - 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**

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

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.