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 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
DOI: https://doi.org/10.1090/S0002-9947-09-04847-8
Published electronically: May 21, 2009
MathSciNet review: 2529915
Full-text PDF Free Access

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
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.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.