Geodesic
On autostability of almost prime models relative to strong constructivizations
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 65 (2010) no. 5, pp. 901-935 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Questions of autostability and algorithmic dimension of models go back to papers by A. I. Malcev and by A. Fröhlich and J. C. Shepherdson in which the effect of the existence of computable presentations which are non-equivalent from the viewpoint of their algorithmic properties was first discovered. Today there are many papers by various authors devoted to investigations of such questions. The present paper deals with the question of inheritance of the properties of autostability and non-autostability relative to strong constructivizations under elementary extensions for almost prime models. Bibliography: 37 titles.
Keywords: computable model, constructive model, strongly constructive model, autostability, prime model, almost prime model, Ehrenfeucht theory, decidable theory, decidable model. 
@article{RM_2010_65_5_a3,
     author = {S. S. Goncharov},
     title = {On autostability of almost prime models relative to strong constructivizations},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {901--935},
     year = {2010},
     volume = {65},
     number = {5},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RM_2010_65_5_a3/}
}
TY  - JOUR
AU  - S. S. Goncharov
TI  - On autostability of almost prime models relative to strong constructivizations
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2010
SP  - 901
EP  - 935
VL  - 65
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/RM_2010_65_5_a3/
LA  - en
ID  - RM_2010_65_5_a3
ER  - 
%0 Journal Article
%A S. S. Goncharov
%T On autostability of almost prime models relative to strong constructivizations
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2010
%P 901-935
%V 65
%N 5
%U http://geodesic.mathdoc.fr/item/RM_2010_65_5_a3/
%G en
%F RM_2010_65_5_a3
S. S. Goncharov. On autostability of almost prime models relative to strong constructivizations. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 65 (2010) no. 5, pp. 901-935. http://geodesic.mathdoc.fr/item/RM_2010_65_5_a3/

[1] A. I. Mal'tsev, “Constructive algebras. I”, Russian Math. Surveys, 16:3 (1961), 77–129 | DOI | MR | Zbl

[2] A. I. Mal'tsev, “On recursive Abelian groups”, Dokl. Math., 32 (1962), 1431–1434 | MR | Zbl

[3] A. Fröhlich, J. C. Shepherdson, “Effective procedures in field theory”, Philos. Trans. Roy. Soc. London. Ser. A, 248:950 (1956), 407–432 | DOI | MR | Zbl

[4] Yu. L. Ershov, “Konstruktivnye modeli”, Izbrannye voprosy algebry i logiki, Nauka, Novosibirsk, 1973, 111–130 | Zbl

[5] M. Morley, “Decidable models”, Israel J. Math., 25:3–4 (1976), 233–240 | MR | Zbl

[6] A. T. Nurtazin, “Strong and weak constructivizations, and enumerable families”, Algebra Logic, 13:3 (1974), 177–184 | MR | Zbl

[7] Yu. L. Ershov, S. S. Goncharov, Constructive models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000, xii+293 pp. | MR | Zbl | Zbl

[8] C. J. Ash, T. S. Millar, “Persistently finite, persistently arithmetic theories”, Proc. Amer. Math. Soc., 89:3 (1983), 487–492 | DOI | MR | Zbl

[9] E. B. Fokina, “O spektrakh vychislimykh modelei”, Vestn. NGU. Ser. matem., mekh., inform., 6:4 (2006), 69–73

[10] E. B. Fokina, “Arithmetic Turing degrees and categorical theories of computable models”, Mathematical logic in Asia, World Sci. Publ., Hackensack, NJ, 2006, 58–69 | MR | Zbl

[11] A. Gavryushkin, “On complexity of Ehrenfeucht theories with computable model”, Logical Approaches to Computational Barriers (Second Conference on Computability in Europe), Report Series, Swansea Univ., 2006, 105–108

[12] A. N. Gavryushkin, “Complexity of Ehrenfeucht models”, Algebra Logic, 45:5 (2006), 289–295 | DOI | MR | Zbl

[13] A. Gavryushkin, “Computable models spectra of Ehrenfeucht theories”, Logic Colloquium 2007, Book of Abstracts, Uniwersytet Wrocławski, 2007, 46–47

[14] A. N. Gavryushkin, “Spectra of computable models for Ehrenfeucht theories”, Algebra Logic, 46:3 (2007), 149–157 | DOI | MR | Zbl

[15] A. Gavryushkin, “Computable models spectra of Ehrenfeucht theories”, Logic and Theory of Algorithms (Fourth Conference on Computability in Europe), CiE 2008 Local Proceedings, University of Athens, 2008, 50–51

[16] A. N. Gavryushkin, “O konstruktivnykh modelyakh teorii s lineinym poryadkom Rudina–Keislera”, Vestn. NGU. Ser. matem., mekh., inform., 9:2 (2009), 30–37

[17] S. Goncharov, B. Khoussainov, “Open problems in the theory of constructive algebraic systems”, Computability theory and its applications (Boulder, CO, 1999), Contemp. Math., 257, Amer. Math. Soc., Providence, RI, 2000, 145–170 | MR | Zbl

[18] J. F. Knight, “Nonarithmetical $\aleph_0$-categorical theories with recursive models”, J. Symbolic Logic, 59:1 (1994), 106–112 | DOI | MR | Zbl

[19] S. Lempp, T. Slaman, “The complexity of the index sets of $\aleph_{0}$-categorical theories and of Ehrenfeucht theories”, Advances in logic, Contemp. Math., 425, Amer. Math. Soc., Providence, RI, 2007, 43–47 | MR | Zbl

[20] T. S. Millar, “Foundations of recursive model theory”, Ann. Math. Logic, 13:1 (1978), 45–72 | DOI | MR | Zbl

[21] T. Millar, “Persistently finite theories with hyperarithmetic models”, Trans. Amer. Math. Soc., 278:1 (1983), 91–99 | MR | Zbl

[22] T. S. Millar, “Decidability and the number of countable models”, Ann. Pure Appl. Logic, 27:2 (1984), 137–153 | DOI | MR | Zbl

[23] T. Millar, “Decidable Ehrenfeucht theories”, Recursion theory (Ithaca, NY, 1982), Proc. Sympos. Pure Math., 42, Amer. Math. Soc., Providence, RI, 1985, 311–321 | MR | Zbl

[24] E. A. Palyutin, “On algebras of formulas for denumerably categorical theories”, Colloq. Math., 31:2 (1974), 157–159 | Zbl

[25] M. G. Peretyat'kin, “On complete theories with a finite number of denumerable models”, Algebra Logic, 12 (1973), 310–326 | Zbl

[26] R. C. Reed, “A decidable Ehrenfeucht theory with exactly two hyperarithmetic models”, Ann. Pure Appl. Logic, 53:2 (1991), 135–168 | DOI | MR | Zbl

[27] J. H. Schmerl, “A decidable $\aleph_{0}$-categorical theory with a nonrecursive Ryll-Nardzewski function”, Fund. Math., 98:2 (1978), 121–125 | MR | Zbl

[28] R. L. Vaught, “Denumerable models of complete theories”, Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw, 1959), Pergamon, Oxford; Państwowe Wydawnictwo Naukowe, Warszawa, 1961, 303–321 | MR | Zbl

[29] S. S. Goncharov, Countable Boolean algebras and decidability, Siberian School Algebra Logic, Consultants Bureau, New York, 1997, 318 pp. | MR | MR | Zbl | Zbl

[30] H. Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill, Toronto–London–New York, 1967, 482 pp. | MR | MR | Zbl | Zbl

[31] C. C. Chang, H. J. Keisler, Model theory, Stud. Logic Found. Math., 73, North-Holland, Amsterdam–London; American Elsevier, New York, 1973, 550 pp. | MR | MR | Zbl

[32] A. I. Mal'tsev, Algorithms and recursive functions, Wolters-Noordoff, Groningen, 1970, 372 pp. | MR | MR | Zbl

[33] S. S. Goncharov, A. T. Nurtazin, “Constructive models of complete solvable theories”, Algebra Logic, 12 (1974), 67–77 | MR | Zbl | Zbl

[34] L. Harrington, “Recursively presented prime models”, J. Symbolic Logic, 39:2 (1974), 305–309 | DOI | MR | Zbl

[35] S. S. Goncharov, “Autostability of prime models under strong constructivizations”, Algebra Logic, 48:6 (2009), 410–417 | DOI | MR

[36] K. Zh. Kudaibergenov, “Autostability and extension of constructivizations”, Siberian Math. J., 25:5 (1984), 743–749 | DOI | MR | MR | Zbl

[37] B. Khoussainov, A. Nies, R. Shore, “Computable models of theories with few models”, Notre Dame J. Formal Logic, 38:2 (1997), 165–178 | DOI | MR | Zbl