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

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?)

  • 1. Chang, C. C.; Keisler, H. J. [1973], Model Theory, North-Holland, Amsterdam. MR 0409165 (53:12927)
  • 2. Cholak, P. A.; Jockusch, Jr., C. G.; Slaman, T. A. [2001], On the strength of Ramsey's Theorem for pairs. J. Symbolic Logic 66, 1-55. MR 1825173 (2002c:03094)
  • 3. Chong, C. T.; Slaman, T. A.; Yang, Y. [ta], On the strength of Ramsey's theorem for pairs. In preparation.
  • 4. Chong, C. T.; Yang, Y. [1998], Recursion theory in weak fragments of Peano arithmetic: A study of cuts. Proc. Sixth Asian Logic Conference, Beijing 1996, World Scientific, Singapore, 47-65. MR 1789730 (2001g:03111)
  • 5. Chong, C. T.; Yang, Y. [2000], Computability theory in arithmetic: Provability, structure and techniques. Computability Theory and Its Applications: Current Trends and Open Problems, P. Cholak, S. Lempp, M. Lerman and R. A. Shore eds., Contemporary Mathematics 257, AMS, Providence, RI, 73-82. MR 1770735 (2001d:03098)
  • 6. Conidis, C. [2008], Classifying model-theoretic properties, J. Symbolic Logic, 73 885-905. MR 2444274
  • 7. Cooper, S. B. [1972], Jump equivalence of the $ \Delta _{2}^{0}$ hyperhyperimune sets. J. Symbolic Logic 37, 598-600. MR 0360240 (50:12690)
  • 8. Csima, B. F. [2004], Degree spectra of prime models. J. Symbolic Logic 69, 430-442. MR 2058182 (2005d:03067)
  • 9. Csima, B. F.; Hirschfeldt, D. R.; Knight, J.; Soare, R. I. [2004], Bounding prime models. J. Symbolic Logic 69, 1117-1142. MR 2135658 (2005m:03065)
  • 10. Downey, R.; Hirschfeldt, D. R.; Lempp, S.; Solomon, R. [2001], A $ \Delta _{2}^{0}$ set with no infinite low subset in either it or its complement. J. Symbolic Logic 66, 1371-1381. MR 1856748 (2002i:03046)
  • 11. Ershov, Yu. L.; Goncharov, S. S.; Nerode, A.; Remmel, J. B. (eds.); Marek, V. W. (assoc. ed.) [1998], Handbook of Recursive Mathematics, 2 vols., Elsevier, New York.
  • 12. Friedman, H. [1976], Systems of second order arithmetic with restricted induction I (abstract). J. Symbolic Logic 41, 557-558.
  • 13. Goncharov, S. S.; Nurtazin, A. T. [1973], Constructive models of complete decidable theories. Algebra Logic 12, 67-77. MR 0398816 (53:2667)
  • 14. Groszek, M.; Slaman, T. A. [nd], Foundations of the priority method I: finite and infinite injury. Preprint.
  • 15. Hájek, P. [1993], Interpretability and fragments of arithmetic. Arithmetic, Proof Theory, and Computational Complexity (Prague, 1991), Oxford Logic Guides 23, Oxford Univ. Press, New York, 185-196. MR 1236462 (94f:03066)
  • 16. Hájek, P.; Pudlák, P. [1998], Metamathematics of First-Order Arithmetic, second printing. Perspect. Math. Logic, Springer-Verlag, Berlin. MR 1748522 (2000m:03003)
  • 17. Harizanov, V. S. [1998], Pure computable model theory, in Ershov et al. [1998], vol. 1, 3-114. MR 1673621 (2000f:03108)
  • 18. Harrington, L. [1974], Recursively presentable prime models. J. Symbolic Logic 39, 305-309. MR 0351804 (50:4292)
  • 19. Herrmann, E. [2001], Infinite chains and antichains in computable partial orderings. J. Symbolic Logic 66, 923-934. MR 1833487 (2003e:03082)
  • 20. Hirschfeldt, D. R. [2006], Computable trees, prime models, and relative decidability. Proc. Amer. Math. Soc. 134, 1495-1498. MR 2199197 (2007b:03055)
  • 21. Hirschfeldt, D. R.; Shore, R. A. [2007], Combinatorial principles weaker than Ramsey's Theorem for pairs. J. Symbolic Logic 72, 171-206. MR 2298478 (2007m:03115)
  • 22. Hirst, J. L. [1987], Combinatorics in Subsystems of Second Order Arithmetic, Ph.D. Dissertation, The Pennsylvania State University.
  • 23. Jockusch, Jr., C. G. [1972], Ramsey's Theorem and recursion theory. J. Symbolic Logic 37, 268-280. MR 0376319 (51:12495)
  • 24. Jockusch, Jr., C. G.; Soare, R. I. [1972], $ \Pi _{1}^{0}$ classes and degrees of theories. Trans. Amer. Math. Soc. 173 , 33-56. MR 0316227 (47:4775)
  • 25. Jockusch, Jr., C. G.; Stephan, F. [1993], A cohesive set which is not high. Math. Log. Quart. 39, 515-530 (correction in Math. Log. Quart. 43, 569). MR 1270396 (95d:03078)
  • 26. Lerman, M. [1983], Degrees of Unsolvability, Springer-Verlag, Berlin. MR 708718 (85h:03044)
  • 27. Millar, T. S. [1978], Foundations of recursive model theory. Ann. Math. Logic 13, 45-72. MR 482430 (80a:03051)
  • 28. Millar, T. S. [1983], Omitting types, type spectrums, and decidability. J. Symbolic Logic 48, 171-181. MR 693259 (85a:03049)
  • 29. Mytilinaios, M. E. [1989], Finite injury and $ \Sigma _{1}$ -induction. J. Symbolic Logic 54, 212-221. MR 987320 (90i:03067a)
  • 30. Paris, J. B.; Kirby, L. A. S. [1978], $ \Sigma_{n}$-collection schemas in arithmetic. Logic Colloquium '77, Stud. Logic Foundations Math. 96, North-Holland, Amsterdam-New York, 199-209. MR 519815 (81e:03056)
  • 31. Robinson, R. W. [1971], Interpolation and embedding in the recursively enumerable degrees. Ann. Math. (2) 93, 285-314. MR 0274286 (43:51)
  • 32. Simpson, S. G. [1999], Subsystems of Second Order Arithmetic, Perspect. Math. Logic, Springer-Verlag, Berlin. MR 1723993 (2001i:03126)
  • 33. Shore, Richard A., Splitting an $ \alpha$-recursively enumerable set. Trans. Amer. Math. Soc. 204 (1975), 65-77. MR 0379154 (52:60)
  • 34. Soare, R. I. [1987], Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin. MR 882921 (88m:03003)

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: https://doi.org/10.1090/S0002-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.

American Mathematical Society