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.

- C. C. Chang and H. J. Keisler,
*Model theory*, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. Studies in Logic and the Foundations of Mathematics, Vol. 73. 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 https://doi.org/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 https://doi.org/10.1090/conm/257/04028 - Chris J. Conidis,
*Classifying model-theoretic properties*, J. Symbolic Logic**73**(2008), no. 3, 885–905. MR**2444274**, DOI https://doi.org/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 https://doi.org/10.2307/2272750 - Barbara F. Csima,
*Degree spectra of prime models*, J. Symbolic Logic**69**(2004), no. 2, 430–442. MR**2058182**, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/S0049-237X%2898%2980002-5 - Leo Harrington,
*Recursively presentable prime models*, J. Symbolic Logic**39**(1974), 305–309. MR**351804**, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1002/malq.19930390153 - Manuel Lerman,
*Degrees of unsolvability*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1983. Local and global theory. MR**708718** - Terrence S. Millar,
*Foundations of recursive model theory*, Ann. Math. Logic**13**(1978), no. 1, 45–72. MR**482430**, DOI https://doi.org/10.1016/0003-4843%2878%2990030-X - Terrence Millar,
*Omitting types, type spectrums, and decidability*, J. Symbolic Logic**48**(1983), no. 1, 171–181. MR**693259**, DOI https://doi.org/10.2307/2273331 - Michael Mytilinaios,
*Finite injury and $\Sigma _1$-induction*, J. Symbolic Logic**54**(1989), no. 1, 38–49. MR**987320**, DOI https://doi.org/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) Stud. Logic Foundations Math., 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 https://doi.org/10.2307/1970776 - Stephen G. Simpson,
*Subsystems of second order arithmetic*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. MR**1723993** - Richard A. Shore,
*Splitting an $\alpha $-recursively enumerable set*, Trans. Amer. Math. Soc.**204**(1975), 65–77. MR**379154**, DOI https://doi.org/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**

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.