## 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

- C. C. Chang and H. J. Keisler,
*Model theory*, Studies in Logic and the Foundations of Mathematics, Vol. 73, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. MR**0409165** - Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman,
*On the strength of Ramsey’s theorem for pairs*, J. Symbolic Logic**66**(2001), no. 1, 1–55. MR**1825173**, DOI 10.2307/2694910 - Chong, C. T.; Slaman, T. A.; Yang, Y. [ta], On the strength of Ramsey’s theorem for pairs. In preparation.
- C. T. Chong and Yue Yang,
*Recursion theory on weak fragments of Peano arithmetic: a study of definable cuts*, Proceedings of the Sixth Asian Logic Conference (Beijing, 1996) World Sci. Publ., River Edge, NJ, 1998, pp. 47–65. MR**1789730** - C. T. Chong and Yue Yang,
*Computability theory in arithmetic: provability, structure and techniques*, Computability theory and its applications (Boulder, CO, 1999) Contemp. Math., vol. 257, Amer. Math. Soc., Providence, RI, 2000, pp. 73–81. MR**1770735**, DOI 10.1090/conm/257/04028 - Chris J. Conidis,
*Classifying model-theoretic properties*, J. Symbolic Logic**73**(2008), no. 3, 885–905. MR**2444274**, DOI 10.2178/jsl/1230396753 - S. B. Cooper,
*Jump equivalence of the $\Delta ^{0}_{2}$ hyperhyperimmune sets*, J. Symbolic Logic**37**(1972), 598–600. MR**360240**, DOI 10.2307/2272750 - Barbara F. Csima,
*Degree spectra of prime models*, J. Symbolic Logic**69**(2004), no. 2, 430–442. MR**2058182**, DOI 10.2178/jsl/1082418536 - Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight, and Robert I. Soare,
*Bounding prime models*, J. Symbolic Logic**69**(2004), no. 4, 1117–1142. MR**2135658**, DOI 10.2178/jsl/1102022214 - Rod Downey, Denis R. Hirschfeldt, Steffen Lempp, and Reed Solomon,
*A $\Delta ^0_2$ set with no infinite low subset in either it or its complement*, J. Symbolic Logic**66**(2001), no. 3, 1371–1381. MR**1856748**, DOI 10.2307/2695113 - 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. - Friedman, H. [1976], Systems of second order arithmetic with restricted induction I (abstract).
*J. Symbolic Logic***41**, 557–558. - S. S. Gončarov and A. T. Nurtazin,
*Constructive models of complete decidable theories*, Algebra i Logika**12**(1973), 125–142, 243 (Russian). MR**0398816** - Groszek, M.; Slaman, T. A. [nd], Foundations of the priority method I: finite and infinite injury. Preprint.
- Petr Hájek,
*Interpretability and fragments of arithmetic*, Arithmetic, proof theory, and computational complexity (Prague, 1991) Oxford Logic Guides, vol. 23, Oxford Univ. Press, New York, 1993, pp. 185–196. MR**1236462** - Petr Hájek and Pavel Pudlák,
*Metamathematics of first-order arithmetic*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1998. Second printing. MR**1748522** - Valentina S. Harizanov,
*Pure computable model theory*, Handbook of recursive mathematics, Vol. 1, Stud. Logic Found. Math., vol. 138, North-Holland, Amsterdam, 1998, pp. 3–114. MR**1673621**, DOI 10.1016/S0049-237X(98)80002-5 - Leo Harrington,
*Recursively presentable prime models*, J. Symbolic Logic**39**(1974), 305–309. MR**351804**, DOI 10.2307/2272643 - E. Herrmann,
*Infinite chains and antichains in computable partial orderings*, J. Symbolic Logic**66**(2001), no. 2, 923–934. MR**1833487**, DOI 10.2307/2695053 - Denis R. Hirschfeldt,
*Computable trees, prime models, and relative decidability*, Proc. Amer. Math. Soc.**134**(2006), no. 5, 1495–1498. MR**2199197**, DOI 10.1090/S0002-9939-05-08097-4 - Denis R. Hirschfeldt and Richard A. Shore,
*Combinatorial principles weaker than Ramsey’s theorem for pairs*, J. Symbolic Logic**72**(2007), no. 1, 171–206. MR**2298478**, DOI 10.2178/jsl/1174668391 - Hirst, J. L. [1987],
*Combinatorics in Subsystems of Second Order Arithmetic*, Ph.D. Dissertation, The Pennsylvania State University. - Carl G. Jockusch Jr.,
*Ramsey’s theorem and recursion theory*, J. Symbolic Logic**37**(1972), 268–280. MR**376319**, DOI 10.2307/2272972 - Carl G. Jockusch Jr. and Robert I. Soare,
*$\Pi ^{0}_{1}$ classes and degrees of theories*, Trans. Amer. Math. Soc.**173**(1972), 33–56. MR**316227**, DOI 10.1090/S0002-9947-1972-0316227-0 - Carl Jockusch and Frank Stephan,
*A cohesive set which is not high*, Math. Logic Quart.**39**(1993), no. 4, 515–530. MR**1270396**, DOI 10.1002/malq.19930390153 - Manuel Lerman,
*Degrees of unsolvability*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR**708718**, DOI 10.1007/978-3-662-21755-9 - Terrence S. Millar,
*Foundations of recursive model theory*, Ann. Math. Logic**13**(1978), no. 1, 45–72. MR**482430**, DOI 10.1016/0003-4843(78)90030-X - Terrence Millar,
*Omitting types, type spectrums, and decidability*, J. Symbolic Logic**48**(1983), no. 1, 171–181. MR**693259**, DOI 10.2307/2273331 - Michael Mytilinaios,
*Finite injury and $\Sigma _1$-induction*, J. Symbolic Logic**54**(1989), no. 1, 38–49. MR**987320**, DOI 10.2307/2275013 - J. B. Paris and L. A. S. Kirby,
*$\Sigma _{n}$-collection schemas in arithmetic*, Logic Colloquium ’77 (Proc. Conf., Wrocław, 1977) Studies in Logic and the Foundations of Mathematics, vol. 96, North-Holland, Amsterdam-New York, 1978, pp. 199–209. MR**519815** - Robert W. Robinson,
*Interpolation and embedding in the recursively enumerable degrees*, Ann. of Math. (2)**93**(1971), 285–314. MR**274286**, DOI 10.2307/1970776 - Stephen G. Simpson,
*Subsystems of second order arithmetic*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. MR**1723993**, DOI 10.1007/978-3-642-59971-2 - Richard A. Shore,
*Splitting an $\alpha$-recursively enumerable set*, Trans. Amer. Math. Soc.**204**(1975), 65–77. MR**379154**, DOI 10.1090/S0002-9947-1975-0379154-1 - Robert I. Soare,
*Recursively enumerable sets and degrees*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR**882921**, DOI 10.1007/978-3-662-02460-7

## 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