|
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 , and others are equivalent to ACA . One, that every atomic theory has an atomic model, is not provable in RCA but is incomparable with WKL , more than conservative over RCA and strictly weaker than all the combinatorial principles of Hirschfeldt and Shore (2007) that are not conservative over RCA . A priority argument with Shore blocking shows that it is also -conservative over B . We also provide a theorem provable by a finite injury priority argument that is conservative over I but implies I over B , and a type omitting theorem that is equivalent to the principle that for every there is a set that is hyperimmune relative to . Finally, we give a version of the atomic model theorem that is equivalent to the principle that for every there is a set that is not recursive in , and is thus in a sense the weakest possible natural principle not true in the -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
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
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],
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
-induction. J. Symbolic Logic 54, 212-221. MR 987320 (90i:03067a) - 30.
- Paris, J. B.; Kirby, L. A. S. [1978],
-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
-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.
|