Degrees of recursively saturated models
Authors:
Angus Macintyre and David Marker
Journal:
Trans. Amer. Math. Soc. 282 (1984), 539554
MSC:
Primary 03D45; Secondary 03C50, 03C57, 03C62, 03H15
MathSciNet review:
732105
Fulltext 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).
 [A]
James
Ax, The elementary theory of finite fields, Ann. of Math. (2)
88 (1968), 239–271. MR 0229613
(37 #5187)
 [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
(82a:03026)
 [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
(58 #10369)
 [KMM]
L.
Kirby, K.
McAloon, and R.
Murawski, Indicators, recursive saturation and expandability,
Fund. Math. 114 (1981), no. 2, 127–139. MR 643553
(84i:03117)
 [K1]
J. Knight, 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.
 [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 (85i:03144), http://dx.doi.org/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
(83k:03039), http://dx.doi.org/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
(85d:03072), http://dx.doi.org/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,
BerlinNew York, 1981, pp. 143–156. MR 619868
(83g:03044)
 [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.), NorthHolland, 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, NorthHolland, Amsterdam, 1982, pp. 233–242. MR 757032
(85i:03109), http://dx.doi.org/10.1016/S0049237X(08)718871
 [Mi]
Terrence
S. Millar, Foundations of recursive model theory, Ann. Math.
Logic 13 (1978), no. 1, 45–72. MR 482430
(80a:03051), http://dx.doi.org/10.1016/00034843(78)90030X
 [Mo]
Michael
Morley, Decidable models, Israel J. Math. 25
(1976), no. 34, 233–240. MR 0457190
(56 #15405)
 [N]
Mark
Nadel, On a problem of MacDowell and Specker, J. Symbolic
Logic 45 (1980), no. 3, 612–622. MR 583377
(82d:03056), http://dx.doi.org/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
(81j:03051)
 [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
(58 #5177)
 [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
(25 #4993)
 [Sm]
C.
Smoryński, Recursively saturated nonstandard models of
arithmetic, J. Symbolic Logic 46 (1981), no. 2,
259–286. MR
613281 (82i:03045), http://dx.doi.org/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
(82a:03003)
 [A]
 J. Ax, The elementary theory of finite fields, Ann. of Math. (2) 88 (1968). MR 0229613 (37:5187)
 [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. Goncharov, Strong constructivizability of homogeneous models, Algebra i Logika 17 (1978). MR 538302 (82a:03026)
 [H]
 L. Harrington, Building arithmetical models of PA, handwritten notes, Berkeley, 1979.
 [Ho]
 H. Hodes, Uniform upper bounds on ideals of Turing degrees, J. Symbolic Logic 43 (1978). MR 0491096 (58:10369)
 [KMM]
 L. Kirby, K. McAloon and R. Murawski, Indicators, recursive saturation and expandability, Fund. Math. 114 (1982). MR 643553 (84i:03117)
 [K1]
 J. Knight, 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.
 [KLS]
 J. Knight, A. Lachlan and R. Soare, Two theorems on degrees of models of true arithmetic, preprint. MR 745370 (85i:03144)
 [KN1]
 J. Knight and M. Nadel, Expansions of models and Turing degrees, J. Symbolic Logic 47 (1982). MR 666818 (83k:03039)
 [KN2]
 , Models of arithmetic and closed ideals, J. Symbolic Logic (to appear). MR 683158 (85d:03072)
 [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]
 A. Macintyre, The complexity of types in field theory, Logic Year 197980 (M Lerman, J. Schmerl and R. Soare, eds.), SpringerVerlag, Berlin and New York, 1980. MR 619868 (83g:03044)
 [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.), NorthHolland, Amsterdam, 1982.
 [Mac3]
 , Nonstandard analysis and effective estimates, in preparation.
 [M]
 D. Marker, Degrees of models of true arithmetic, Proceedings of the Herbrand Symposium (J. Stern, ed.), NorthHolland, Amsterdam, 1982. MR 757032 (85i:03109)
 [Mi]
 T. Millar, Foundations of recursive model theory, Ann. Math. Logic 13 ( 1978). MR 482430 (80a:03051)
 [Mo]
 M. Morley, Decidable models, Israel J. Math. 25 (1976). MR 0457190 (56:15405)
 [N]
 M. Nadel, On a problem of MacDowell and Specker, 3. Symbolic Logic 45 ( 1980). MR 583377 (82d:03056)
 [P]
 M. G. Peretyat'kin, Criterion for strong constructivizability of a homogeneous model, Algebra i Logika 17 (1978). MR 538306 (81j:03051)
 [Sch]
 J. Schlipf, A guide to the identification of admissible sets over structures, Ann. Math. Logic 12 (1978). MR 0485330 (58:5177)
 [S]
 D. Scott, Algebras of sets binumerable in complete extensions of arithmetic, Proc. Sympos. Pure Math., vol. 5, Amer. Math. Soc., Providence, R.I., 1962. MR 0141595 (25:4993)
 [Sm]
 C. Smorynski, Recursively saturated nonstandard models of arithmetic, J. Symbolic Logic 45 (1981). MR 613281 (82i:03045)
 [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]
 , Minimally saturated models, Model Theory of Algebra and Arithmetic (Karpacz 1979) (L. Pacholski, J. Wierzejewski and A. J. Wilkie, eds.), SpringerVerlag, Berlin and New York, 1981. MR 606775 (82a:03003)
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/S00029947198407321055
PII:
S 00029947(1984)07321055
Keywords:
Scott set,
Turing degree,
recursively saturated model,
model of arithmetic
Article copyright:
© Copyright 1984
American Mathematical Society
