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 atomic model theorem and type omitting
HTML articles powered by AMS MathViewer

by Denis R. Hirschfeldt, Richard A. Shore and Theodore A. Slaman PDF
Trans. Amer. Math. Soc. 361 (2009), 5805-5837 Request permission

Abstract:

We investigate the complexity of several classical model theoretic theorems about prime and atomic models and omitting types. Some are provable in RCA$_{0}$, and others are equivalent to ACA$_{0}$. One, that every atomic theory has an atomic model, is not provable in RCA$_{0}$ but is incomparable with WKL$_{0}$, more than $\Pi _{1}^{1}$ conservative over RCA$_{0}$ and strictly weaker than all the combinatorial principles of Hirschfeldt and Shore (2007) that are not $\Pi _{1}^{1}$ conservative over RCA$_{0}$. A priority argument with Shore blocking shows that it is also $\Pi _{1}^{1}$-conservative over B$\Sigma _{2}$. We also provide a theorem provable by a finite injury priority argument that is conservative over I$\Sigma _{1}$ but implies I$\Sigma _{2}$ over B$\Sigma _{2}$, and a type omitting theorem that is equivalent to the principle that for every $X$ there is a set that is hyperimmune relative to $X$. Finally, we give a version of the atomic model theorem that is equivalent to the principle that for every $X$ there is a set that is not recursive in $X$, and is thus in a sense the weakest possible natural principle not true in the $\omega$-model consisting of the recursive sets.
References
Similar Articles
Additional Information
  • Denis R. Hirschfeldt
  • Affiliation: Department of Mathematics, University of Chicago, Chicago, Illinois 60637
  • MR Author ID: 667877
  • Email: drh@math.uchicago.edu
  • Richard A. Shore
  • Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
  • MR Author ID: 161135
  • Email: shore@math.cornell.edu
  • Theodore A. Slaman
  • Affiliation: Department of Mathematics, University of California, Berkeley, Berkeley, California 94720
  • MR Author ID: 163530
  • Email: slaman@math.berkeley.edu
  • Received by editor(s): July 25, 2007
  • Published electronically: May 21, 2009
  • Additional Notes: The first author’s research was partially supported by NSF Grants DMS-0200465 and DMS-0500590.
    The second author’s research was partially supported by NSF Grants DMS-0100035 and DMS-0554855.
    The third author’s research was partially supported by NSF Grants DMS-9988644 and DMS-0501167.
  • © Copyright 2009 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Trans. Amer. Math. Soc. 361 (2009), 5805-5837
  • MSC (2000): Primary 03B30, 03C15, 03C50, 03C57, 03D45, 03F35
  • DOI: https://doi.org/10.1090/S0002-9947-09-04847-8
  • MathSciNet review: 2529915