×

Degrees of autostability relative to strong constructivizations. (English. Russian original) Zbl 1294.03025

Proc. Steklov Inst. Math. 274, 105-115 (2011); translation from Tr. Mat. Inst. Steklova 274, 119-129 (2011).
Summary: The spectra of the Turing degrees of autostability of computable models are studied. For almost prime decidable models, it is shown that the autostability spectrum relative to strong constructivizations of such models always contains a certain recursively enumerable Turing degree; moreover, it is shown that for any recursively enumerable Turing degree, there exist prime models in which this degree is the least one in the autostability spectrum relative to strong constructivizations.

MSC:

03C57 Computable structure theory, computable model theory
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] A. I. Mal’tsev, ”On Recursive Abelian Groups,” Dokl. Akad. Nauk SSSR 146(5), 1009–1012 (1962) [Sov. Math., Dokl. 32, 1431–1434 (1963)].
[2] A. I. Mal’tsev, ”Constructive Algebras. I,” Usp. Mat. Nauk 16(3), 3–60 (1961) [Russ. Math. Surv. 16 (3), 77–129 (1961)].
[3] A. Fröhlich and J. C. Shepherdson, ”Effective Procedures in Field Theory,” Philos. Trans. R. Soc. London, Ser. A 248, 407–432 (1956). · Zbl 0070.03502
[4] S. I. Adyan, ”Unsolvability of Some Algorithmic Problems in the Theory of Groups,” Tr. Mosk. Mat. Obshch. 6, 231–298 (1957).
[5] S. I. Adyan, ”The Problem of Identity in Associative Systems of a Special Form,” Dokl. Akad. Nauk SSSR 135(6), 1297–1300 (1960) [Sov. Math., Dokl. 1, 1360–1363 (1960)].
[6] P. S. Novikov and S. I. Adyan, ”Das Wortproblem für Halbgruppen mit einseitiger Kürzungsregel,” Z. Math. Log. Grundlagen Math. 4, 66–88 (1958). · Zbl 0080.24102
[7] A. A. Markov, ”Impossibility of Certain Algorithms in the Theory of Associative Systems. II,” Dokl. Akad. Nauk SSSR 58(3), 353–356 (1947). · Zbl 0030.19401
[8] B. L. van der Waerden, ”Eine Bemerkung über die Unzerlegbarkeit von Polynomen,” Math. Ann. 102, 738–739 (1930). · JFM 56.0825.05
[9] S. S. Goncharov, ”Constructivizability of Superatomic Boolean Algebras,” Algebra Logika 12(1), 31–40 (1973) [Algebra Logic 12, 17–22 (1973)].
[10] S. Wehner, ”Enumerations, Countable Structures and Turing Degrees,” Proc. Am. Math. Soc. 126, 2131–2139 (1998). · Zbl 0906.03044
[11] T. A. Slaman, ”Relative to Any Nonrecursive Set,” Proc. Am. Math. Soc. 126, 2117–2122 (1998). · Zbl 0894.03017
[12] S. S. Goncharov, ”Limit Equivalent Constructivizations,” in Mathematical Logic and the Theory of Algorithms (Nauka, Novosibirsk, 1982), Tr. Inst. Mat., Sib. Otd. Akad. Nauk SSSR 2, pp. 4–12.
[13] S. Goncharov, V. Harizanov, J. Knight, C. McCoy, R. Miller, and R. Solomon, ”Enumerations in Computable Structure Theory,” Ann. Pure Appl. Logic 136(3), 219–246 (2005). · Zbl 1081.03033
[14] S. S. Goncharov, ”Computability and Computable Models,” in Mathematical Problems from Applied Logic. II, Ed. by D. Gabbay, S. S. Goncharov, and M. Zakharyashev (Springer, New York, 2007), Int. Math. Ser. 5, pp. 99–216. · Zbl 1143.03017
[15] C. J. Ash, ”Categoricity in Hyperarithmetical Degrees,” Ann. Pure Appl. Logic 34(1), 1–14 (1987). · Zbl 0617.03016
[16] C. J. Ash and J. F. Khight, Computable Structures and the Hyperarithmetical Hierarchy (Elsevier, Amsterdam, 2000). · Zbl 0960.03001
[17] C. Ash, J. Knight, M. Manasse, and T. Slaman, ”Generic Copies of Countable Structures,” Ann. Pure Appl. Logic 42(3), 195–205 (1989). · Zbl 0678.03012
[18] J. Chisholm, E. B. Fokina, S. S. Goncharov, V. S. Harizanov, J. F. Knight, and S. Quinn, ”Intrinsic Bounds on Complexity and Definability at Limit Levels,” J. Symb. Logic 74(3), 1047–1060 (2009). · Zbl 1201.03019
[19] E. B. Fokina, I. Kalimullin, and R. Miller, ”Degrees of Categoricity of Computable Structures,” Arch. Math. Logic 49, 51–67 (2010). · Zbl 1184.03026
[20] Yu. L. Ershov, ”Constructive Models,” in Selected Topics of Algebra and Logic (Nauka, Novosibirsk, 1973), pp. 111–130 [in Russian].
[21] M. D. Morley, ”Decidable Models,” Isr. J. Math. 25, 233–240 (1976). · Zbl 0361.02067
[22] S. S. Goncharov and A. T. Nurtazin, ”Constructive Models of Complete Solvable Theories,” Algebra Logika 12(2), 125–142 (1973) [Algebra Logic 12, 67–77 (1973)]. · Zbl 0288.02022
[23] Yu. Ershov and S. Goncharov, ”Elementary Theories and Their Constructive Models,” in Handbook of Recursive Mathematics, Vol. 1: Recursive Model Theory (Elsevier, Amsterdam, 1998), Stud. Logic Found. Math. 138, pp. 115–165. · Zbl 0952.03036
[24] A. T. Nurtazin, ”Strong andWeak Constructivization and Computable Families,” Algebra Logika 13(3), 311–323 (1974) [Algebra Logic 13, 177–184 (1974)]. · Zbl 0305.02061
[25] L. Harrington, ”Recursively Presentable Prime Models,” J. Symb. Logic 39, 305–309 (1974). · Zbl 0332.02055
[26] T. S. Millar, ”Foundations of Recursive Model Theory,” Ann. Math. Logic 13(1), 45–72 (1978). · Zbl 0432.03018
[27] J. Chisholm, ”Effective Model Theory vs. Recursive Model Theory,” J. Symb. Logic 55(3), 1168–1191 (1990). · Zbl 0722.03030
[28] S. S. Goncharov, Countable Boolean Algebras and Decidability (Nauchnaya Kniga, Novosibirsk, 1996; Plenum, New York, 1997). · Zbl 0902.03021
[29] S. S. Goncharov and Yu. L. Ershov, Constructive Models (Nauchnaya Kniga, Novosibirsk, 1999); Engl. transl.: Yu. L. Ershov and S. S. Goncharov, Constructive Models (Consultants Bureau, New York, 2000).
[30] S. S. Goncharov, ”Autostability of Prime Models under Strong Constructivizations,” Algebra Logika 48(6), 729–740 (2009) [Algebra Logic 48, 410–417 (2009)]. · Zbl 1241.03043
[31] S. S. Goncharov, ”On Autostability of Almost Prime Models Relative to Strong Constructivizations,” Usp. Mat. Nauk 65(5), 107–142 (2010) [Russ. Math. Surv. 65, 901–935 (2010)]. · Zbl 1219.03038
[32] H. Rogers, Jr., Theory of Recursive Functions and Effective Computability (McGraw-Hill, Maidenhead, Berksh., 1967; Mir, Moscow, 1972).
[33] C. C. Chang and H. J. Keisler, Model Theory (North-Holland, Amsterdam, 1973; Mir, Moscow, 1977).
[34] A. I. Mal’cev, Algorithms and Recursive Functions (Nauka, Moscow, 1965; Wolters-Noordhoff, Groningen, 1970).
[35] E. A. Palyutin, ”The Algebras of Formulae of Countably Categorical Theories,” Colloq. Math. 31(2), 157–159 (1974). · Zbl 0295.02029
[36] S. S. Goncharov and J. F. Knight, ”Computable Structure and Non-structure Theorems,” Algebra Logika 41(6), 639–681 (2002) [Algebra Logic 41, 351–373 (2002)]. · Zbl 1034.03044
[37] Yu. L. Ershov, Decision Problems and Constructive Models (Nauka, Moscow, 1980) [in Russian]. · Zbl 0495.03009
[38] C. F. D. McCoy, ”{\(\Delta\)}02 -Categoricity in Boolean Algebras and Linear Orderings,” Ann. Pure Appl. Logic 119(1–3), 85–120 (2003). · Zbl 1016.03036
[39] C. F. D. McCoy, ”Partial Results in {\(\Delta\)} 3 0 -Categoricity in Linear Orderings and Boolean Algebras,” Algebra Logika 41(5), 531–552 (2002) [Algebra Logic 41, 295–305 (2002)]. · Zbl 1008.03023
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.