×

zbMATH — the first resource for mathematics

Autostability of prime models under strong constructivizations. (English. Russian original) Zbl 1241.03043
Algebra Logic 48, No. 6, 410-417 (2009); translation from Algebra Logika 48, No. 6, 729-740 (2009).
Summary: We furnish an example of an Ehrenfeucht theory whose prime model is autostable under strong constructivizations and there exists a prime model in a finite expansion by constants that is nonautostable under strong constructivizations of the theory constructed.

MSC:
03C57 Computable structure theory, computable model theory
03C15 Model theory of denumerable and separable structures
03D45 Theory of numerations, effectively presented structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. Fröhlich and J. Shepherdson, ”Effective procedures in field theory,” Philos. Trans. Roy. Soc. London, Ser. A, 248, 407-432 (1956). · Zbl 0070.03502
[2] A. I. Mal’tsev, ”On recursive Abelian groups,” Dokl. Akad. Nauk SSSR, 146, No. 5, 1009-1012 (1962).
[3] A. I. Mal’tsev, ”Constructive models. I,” Usp. Mat. Nauk, 16, No. 3, 3-60 (1961).
[4] E. B. Fokina, ”Arithmetical Turing degrees and categorical theories of computable models,” in Mathematical Logic in Asia, Proc. 9th Asian Logic Conf. (2006), pp. 58-69. · Zbl 1116.03028
[5] S. S. Goncharov and Yu. L. Ershov, Constructive Models, Sib. School Alg. Log. [in Russian], Nauch. Kniga, Novosibirsk (1999). · Zbl 1043.03518
[6] E. B. Fokina, ”Spectra of computable models,” Vestnik NGU, Mat., Mekh., Inf., 6, No. 6, 69-73 (2006). · Zbl 1116.03028
[7] J. H. Schmerl, ”A decidable 0-categorical theory with a non-recursive Ryll-Nardzewski function,” Fund. Math., 98, No. 2, 121-125 (1978). · Zbl 0372.02025
[8] A. Gavryushkin, ”On complexity of Ehrenfeucht theories with computable model,” in Logical Approaches to Computational Barriers, Second Conf. Comput. Europe, Rep. Ser., Swansea Univ. (2006), pp. 105-108. · Zbl 1164.03327
[9] A. N. Gavryushkin, ”Complexity of Ehrenfeucht models,” Algebra Logika, 46, No. 5, 507-519 (2006). · Zbl 1164.03327
[10] M. G. Peretyatkin, ”Complete theories with finite number of countable models,” Algebra Logika, 12, No. 5, 550-576 (1973).
[11] S. Goncharov and B. Khoussainov, ”Open problems in the theory of constructive algebraic systems,” Cont. Math., 257, Am. Math. Soc., Providence, RI (2000), pp. 145-170. · Zbl 0961.03037
[12] T. S. Millar, ”Foundations of recursive model theory,” Ann. Math. Log., 13, No. 1, 45-72 (1978). · Zbl 0432.03018
[13] T. Millar, ”Persistently finite theories with hyperarithmetic models,” Trans. Am. Math. Soc., 278, No. 1, 91-99 (1983). · Zbl 0525.03027
[14] T. Millar, ”Decidability and the number of countable models,” Ann. Pure Appl. Log., 27, No. 2, 137-153 (1984). · Zbl 0563.03014
[15] T. Millar, ”Decidable Ehrenfeucht theories,” Proc. Symp. Pure Math., 42 (1985), pp. 311-321. · Zbl 0573.03003
[16] J. Knight, ”Nonarithmetical 0-categorical theories with recursive models,” J. Symb. Log., 59, No. 1, 106-112 (1994). · Zbl 0804.03021
[17] R. Reed, ”A decidable Ehrenfeucht theory with exactly two hyperarithmetic models,” Ann. Pure Appl. Log., 53, No. 2, 135-168 (1991). · Zbl 0733.03021
[18] C. Ash and T. Millar, ”Persistently finite, persistently arithmetic theories,” Proc. Am. Math. Soc., 89, 487-492 (1983). · Zbl 0527.03014
[19] M. Lerman and J. Scmerl, ”Theories with recursive models,” J. Symb. Log., 44, No. 1, 59-76 (1979). · Zbl 0423.03038
[20] S. Lempp and T. A. Slaman, ”The complexity of the index sets of 0-categorical theories and of Ehrenfeucht theories,” Cont. Math., 425, Am. Math. Soc., Providence, RI (2007), pp. 43-47. · Zbl 1123.03035
[21] M. Morley, ”Decidable models,” Israel J. Math., 25, 233-240 (1976). · Zbl 0361.02067
[22] R. Vaught, ”Denumerable models of complete theories,” in Infinitistic Methods, Proc. Symp. Found. Math., Pergamon, London (1961), pp. 303-321. · Zbl 0113.24302
[23] S. S. Goncharov, ”Strong constructivizability of homogeneous models,” Algebra Logika, 17, No. 4, 363-388 (1978). · Zbl 0441.03015
[24] M. G. Peretyatkin, ”A strong constructivizability criterion for homogeneous models,” Algebra Logika, 17, No. 4, 436-454 (1978).
[25] A. N. Gavryushkin, ”Spectra of computable models for Ehrenfeucht theories,” Algebra Logika, 46, No. 3, 275-289 (2007). · Zbl 1164.03328
[26] A. N. Gavryushkin, ”Constructive models of theories with linear Rudin–Keisler ordering” Vestnik NGU, Mat., Mekh., Inf., 9, No. 2, 30-37 (2009). · Zbl 1249.03055
[27] A. Gavryushkin, ”Computable models spectra of Ehrenfeucht theories,” in Logic Coll. 2007, Uniw. Wroclawski (2007), pp. 46-47. · Zbl 1164.03328
[28] A. Gavryushkin, ”Computable models spectra of Ehrenfeucht theories,” in Logic and Theory of Algorithms, Fourth Conf. Comput. Europe, Univ. Athens (2008), pp. 50-51.
[29] H. Rogers, Theory of Recursive Functions and Effective Computability, McGraw-Hill, New York (1967). · Zbl 0183.01401
[30] C. C. Chang and H. J. Keisler, Model Theory, North-Holland, Amsterdam (1973).
[31] A. T. Nurtazin, ”Strong and weak constructivizations and computable families,” Algebra Logika, 13, No. 3, 311-323 (1974). · Zbl 0305.02061
[32] E. A. Palyutin, ”Algebras of formulas for countably categorical theories,” Coll. Math., 31, 157-159 (1974). · Zbl 0295.02029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.