Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)

     

The atomic model theorem and type omitting

Author(s): Denis R. Hirschfeldt; Richard A. Shore; Theodore A. Slaman
Journal: Trans. Amer. Math. Soc. 361 (2009), 5805-5837.
MSC (2000): Primary 03B30, 03C15, 03C50, 03C57, 03D45, 03F35
Posted: May 21, 2009
MathSciNet review: 2529915
Retrieve article in: 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:

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: 10.1090/S0002-9947-09-04847-8
PII: S 0002-9947(09)04847-8
Received by editor(s): July 25, 2007
Posted: 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 of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia