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