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 is -saturated for some Scott set , and is an enumeration of , then has a presentation recursive in . 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**).

**[**James Ax,**A**]*The elementary theory of finite fields*, Ann. of Math. (2)**88**(1968), 239–271. MR**0229613****[**P. Cegielski, K. McAloon and G. Wilmers,**CMW**]*Modeles recursivement satures de l'addition et de la multiplication des entiers naturels*, preprint.**[**S. S. Gončarov,**G**]*Strong constructivizability of homogeneous models*, Algebra i Logika**17**(1978), no. 4, 363–388, 490 (Russian). MR**538302****[**L. Harrington,**H**]*Building arithmetical models of PA*, handwritten notes, Berkeley, 1979.**[**Harold T. Hodes,**Ho**]*Uniform upper bounds on ideals of Turing degrees*, J. Symbolic Logic**43**(1978), no. 3, 601–612. MR**0491096****[**L. Kirby, K. McAloon, and R. Murawski,**KMM**]*Indicators, recursive saturation and expandability*, Fund. Math.**114**(1981), no. 2, 127–139. MR**643553****[**J. Knight,**K1**]*Additive structure in uncountable models for a fixed completion of*, J. Symbolic Logic (to appear).**[**-,**K2**]*A nonstandard model of arithmetic of degree less than that of true arithmetic*, handwritten notes, Notre Dame, 1978.**[**Julia Knight, Alistair H. Lachlan, and Robert I. Soare,**KLS**]*Two theorems on degrees of models of true arithmetic*, J. Symbolic Logic**49**(1984), no. 2, 425–436. MR**745370**, 10.2307/2274174**[**Julia Knight and Mark Nadel,**KN1**]*Expansions of models and Turing degrees*, J. Symbolic Logic**47**(1982), no. 3, 587–604. MR**666818**, 10.2307/2273590**[**Julia Knight and Mark Nadel,**KN2**]*Models of arithmetic and closed ideals*, J. Symbolic Logic**47**(1982), no. 4, 833–840 (1983). MR**683158**, 10.2307/2273102**[**H. Lessan,**L**]*Models of arithmetic*, Ph.D. thesis, Manchester University, 1978.**[**L. Lipschitz and M. Nadel,**LN**]*The additive structure of models of PA*, Proc. Amer. Math. Soc.**68**(1978).**[**Angus Macintyre,**Mac1**]*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*, 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.**[**David Marker,**M**]*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**[**Terrence S. Millar,**Mi**]*Foundations of recursive model theory*, Ann. Math. Logic**13**(1978), no. 1, 45–72. MR**482430**, 10.1016/0003-4843(78)90030-X**[**Michael Morley,**Mo**]*Decidable models*, Israel J. Math.**25**(1976), no. 3-4, 233–240. MR**0457190****[**Mark Nadel,**N**]*On a problem of MacDowell and Specker*, J. Symbolic Logic**45**(1980), no. 3, 612–622. MR**583377**, 10.2307/2273426**[**M. G. Peretjat′kin,**P**]*A criterion of strong constructivizability of a homogeneous model*, Algebra i Logika**17**(1978), no. 4, 436–454, 491 (Russian). MR**538306****[**John S. Schlipf,**Sch**]*A guide to the identification of admissible sets above structures*, Ann. Math. Logic**12**(1977), no. 2, 151–192. MR**0485330****[**Dana Scott,**S**]*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****[**C. Smoryński,**Sm**]*Recursively saturated nonstandard models of arithmetic*, J. Symbolic Logic**46**(1981), no. 2, 259–286. MR**613281**, 10.2307/2273620**[**R. Solovay, personal communication, 1982.**So**]**[**S. Tennenbaum,**T**]*Nonarchimedean models of arithmetic*, Notices Amer. Math. Soc.**6**(1979).**[**G. Wilmers, Ph.D. thesis, Oxford, 1975.**W1**]**[**L. Pacholski and J. Wierzejewski (eds.),**W2**]*Model theory of algebra and arithmetic*, Lecture Notes in Mathematics, vol. 834, Springer, Berlin, 1980. MR**606775**

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