Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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