Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 

 

Degrees of recursively saturated models


Authors: Angus Macintyre and David Marker
Journal: Trans. Amer. Math. Soc. 282 (1984), 539-554
MSC: Primary 03D45; Secondary 03C50, 03C57, 03C62, 03H15
MathSciNet review: 732105
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Using relativizations of results of Goncharov and Peretyat'kin on decidable homogeneous models, we prove that if $ M$ is $ S$-saturated for some Scott set $ S$, and $ F$ is an enumeration of $ S$, then $ M$ has a presentation recursive in $ F$. Applying this result we are able to classify degrees coding (i) the reducts of models of PA to addition or multiplication, (ii) internally finite initial segments and (iii) nonstandard residue fields. We also use our results to simplify Solovay's characterization of degrees coding nonstandard models of Th(N).


References [Enhancements On Off] (What's this?)

  • [A] James Ax, The elementary theory of finite fields, Ann. of Math. (2) 88 (1968), 239–271. MR 0229613
  • [CMW] P. Cegielski, K. McAloon and G. Wilmers, Modeles recursivement satures de l'addition et de la multiplication des entiers naturels, preprint.
  • [G] S. S. Gončarov, Strong constructivizability of homogeneous models, Algebra i Logika 17 (1978), no. 4, 363–388, 490 (Russian). MR 538302
  • [H] L. Harrington, Building arithmetical models of PA, handwritten notes, Berkeley, 1979.
  • [Ho] Harold T. Hodes, Uniform upper bounds on ideals of Turing degrees, J. Symbolic Logic 43 (1978), no. 3, 601–612. MR 0491096
  • [KMM] L. Kirby, K. McAloon, and R. Murawski, Indicators, recursive saturation and expandability, Fund. Math. 114 (1981), no. 2, 127–139. MR 643553
  • [K1] J. Knight, Additive structure in uncountable models for a fixed completion of $ P$, J. Symbolic Logic (to appear).
  • [K2] -, A nonstandard model of arithmetic of degree less than that of true arithmetic, handwritten notes, Notre Dame, 1978.
  • [KLS] Julia Knight, Alistair H. Lachlan, and Robert I. Soare, Two theorems on degrees of models of true arithmetic, J. Symbolic Logic 49 (1984), no. 2, 425–436. MR 745370, 10.2307/2274174
  • [KN1] Julia Knight and Mark Nadel, Expansions of models and Turing degrees, J. Symbolic Logic 47 (1982), no. 3, 587–604. MR 666818, 10.2307/2273590
  • [KN2] Julia Knight and Mark Nadel, Models of arithmetic and closed ideals, J. Symbolic Logic 47 (1982), no. 4, 833–840 (1983). MR 683158, 10.2307/2273102
  • [L] H. Lessan, Models of arithmetic, Ph.D. thesis, Manchester University, 1978.
  • [LN] L. Lipschitz and M. Nadel, The additive structure of models of PA, Proc. Amer. Math. Soc. 68 (1978).
  • [Mac1] Angus Macintyre, The complexity of types in field theory, Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80) Lecture Notes in Math., vol. 859, Springer, Berlin-New York, 1981, pp. 143–156. MR 619868
  • [Mac2] -, Residue fields of models of $ P$, Logic, Methodology and Philosophy of Science. VI (Hannover 1979) (L. Cohen, J. Los, H. Pfeiffer and K. Podewski, eds.), North-Holland, Amsterdam, 1982.
  • [Mac3] -, Nonstandard analysis and effective estimates, in preparation.
  • [M] David Marker, Degrees of models of true arithmetic, Proceedings of the Herbrand symposium (Marseilles, 1981) Stud. Logic Found. Math., vol. 107, North-Holland, Amsterdam, 1982, pp. 233–242. MR 757032, 10.1016/S0049-237X(08)71887-1
  • [Mi] Terrence S. Millar, Foundations of recursive model theory, Ann. Math. Logic 13 (1978), no. 1, 45–72. MR 482430, 10.1016/0003-4843(78)90030-X
  • [Mo] Michael Morley, Decidable models, Israel J. Math. 25 (1976), no. 3-4, 233–240. MR 0457190
  • [N] Mark Nadel, On a problem of MacDowell and Specker, J. Symbolic Logic 45 (1980), no. 3, 612–622. MR 583377, 10.2307/2273426
  • [P] M. G. Peretjat′kin, A criterion of strong constructivizability of a homogeneous model, Algebra i Logika 17 (1978), no. 4, 436–454, 491 (Russian). MR 538306
  • [Sch] John S. Schlipf, A guide to the identification of admissible sets above structures, Ann. Math. Logic 12 (1977), no. 2, 151–192. MR 0485330
  • [S] Dana Scott, Algebras of sets binumerable in complete extensions of arithmetic, Proc. Sympos. Pure Math., Vol. V, American Mathematical Society, Providence, R.I., 1962, pp. 117–121. MR 0141595
  • [Sm] C. Smoryński, Recursively saturated nonstandard models of arithmetic, J. Symbolic Logic 46 (1981), no. 2, 259–286. MR 613281, 10.2307/2273620
  • [So] R. Solovay, personal communication, 1982.
  • [T] S. Tennenbaum, Nonarchimedean models of arithmetic, Notices Amer. Math. Soc. 6 (1979).
  • [W1] G. Wilmers, Ph.D. thesis, Oxford, 1975.
  • [W2] L. Pacholski and J. Wierzejewski (eds.), Model theory of algebra and arithmetic, Lecture Notes in Mathematics, vol. 834, Springer, Berlin, 1980. MR 606775

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D45, 03C50, 03C57, 03C62, 03H15

Retrieve articles in all journals with MSC: 03D45, 03C50, 03C57, 03C62, 03H15


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1984-0732105-5
Keywords: Scott set, Turing degree, recursively saturated model, model of arithmetic
Article copyright: © Copyright 1984 American Mathematical Society