Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

The atomic model theorem and type omitting


Authors: Denis R. Hirschfeldt, Richard A. Shore and Theodore A. Slaman
Journal: Trans. Amer. Math. Soc. 361 (2009), 5805-5837
MSC (2000): Primary 03B30, 03C15, 03C50, 03C57, 03D45, 03F35
Published electronically: May 21, 2009
MathSciNet review: 2529915
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 03B30, 03C15, 03C50, 03C57, 03D45, 03F35

Retrieve articles in all journals with MSC (2000): 03B30, 03C15, 03C50, 03C57, 03D45, 03F35


Additional Information

Denis R. Hirschfeldt
Affiliation: Department of Mathematics, University of Chicago, Chicago, Illinois 60637
Email: drh@math.uchicago.edu

Richard A. Shore
Affiliation: Department of Mathematics, Cornell University, Ithaca, New York 14853
Email: shore@math.cornell.edu

Theodore A. Slaman
Affiliation: Department of Mathematics, University of California, Berkeley, Berkeley, California 94720
Email: slaman@math.berkeley.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-09-04847-8
PII: S 0002-9947(09)04847-8
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.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.