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
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.

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

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

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.