Degrees of autostability relative to strong constructivizations

S. S. Goncharov

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 119-129.

Résumé

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.

Bibliographie

[1] Maltsev A.I., “O rekursivnykh abelevykh gruppakh”, DAN SSSR, 146:5 (1962), 1009–1012 | Zbl

[2] Maltsev A.I., “Konstruktivnye algebry. I”, UMN, 16:3 (1961), 3–60 | MR | Zbl

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

[4] Adyan S.I., “Nerazreshimost nekotorykh algoritmicheskikh problem v teorii grupp”, Tr. Mosk. mat. o-va, 6 (1957), 231–298 | MR | Zbl

[5] Adyan S.I., “K probleme tozhdestva v assotsiativnykh sistemakh spetsialnogo vida”, DAN SSSR, 135:6 (1960), 1297–1300 | MR | Zbl

[6] Novikov P.S., Adyan S.I., “Das Wortproblem für Halbgruppen mit einseitiger Kürzungsregel”, Ztschr. Math. Logik Grundl. Math., 4 (1958), 66–88 | DOI | MR | Zbl

[7] Markov A.A., “Nevozmozhnost nekotorykh algorifmov v teorii assotsiativnykh sistem. II”, DAN SSSR, 58:3 (1947), 353–356 | Zbl

[8] van der Waerden B.L., “Eine Bemerkung über die Unzerlegbarkeit von Polynomen”, Math. Ann., 102 (1930), 738–739 | DOI | MR | Zbl

[9] Goncharov S.S., “Konstruktiviziruemost superatomnykh bulevykh algebr”, Algebra i logika, 12:1 (1973), 31–40 | Zbl

[10] Wehner S., “Enumerations, countable structures and Turing degrees”, Proc. Amer. Math. Soc., 126 (1998), 2131–2139 | DOI | MR | Zbl

[11] Slaman T.A., “Relative to any nonrecursive set”, Proc. Amer. Math. Soc., 126 (1998), 2117–2122 | DOI | MR | Zbl

[12] Goncharov S.S., “Predelno ekvivalentnye konstruktivizatsii”, Matematicheskaya logika i teoriya algoritmov, Tr. In-ta matematiki SO AN SSSR, 2, Nauka, Novosibirsk, 1982, 4–12 | MR

[13] Goncharov S., Harizanov V., Knight J., McCoy C., Miller R., Solomon R., “Enumerations in computable structure theory”, Ann. Pure and Appl. Logic, 136:3 (2005), 219–246 | DOI | MR | Zbl

[14] Goncharov S.S., “Computability and computable models”, Mathematical problems from applied logic. II, Intern. Math. Ser., 5, eds. D. Gabbay, S.S. Goncharov, M. Zakharyashev, Springer, New York, 2007, 99–216 | DOI | MR | Zbl

[15] Ash C.J., “Categoricity in hyperarithmetical degrees”, Ann. Pure and Appl. Logic, 34:1 (1987), 1–14 | DOI | MR | Zbl

[16] Ash C.J., Khight J.F., Computable structures and the hyperarithmetical hierarchy, Elsevier, Amsterdam, 2000 | Zbl

[17] Ash C., Knight J., Manasse M., Slaman T., “Generic copies of countable structures”, Ann. Pure and Appl. Logic, 42:3 (1989), 195–205 | DOI | MR | Zbl

[18] Chisholm J., Fokina E.B., Goncharov S.S., Harizanov V.S., Knight J.F., Quinn S., “Intrinsic bounds on complexity and definability at limit levels”, J. Symb. Logic, 74:3 (2009), 1047–1060 | DOI | MR | Zbl

[19] Fokina E.B., Kalimullin I., Miller R., “Degrees of categoricity of computable structures”, Arch. Math. Logic, 49 (2010), 51–67 | DOI | MR | Zbl

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

[21] Morley M.D., “Decidable models”, Israel J. Math., 25 (1976), 233–240 | DOI | MR | Zbl

[22] Goncharov S.S., Nurtazin A.T., “Konstruktivnye modeli polnykh razreshimykh teorii”, Algebra i logika, 12:2 (1973), 125–142 | MR | Zbl

[23] Ershov Yu., Goncharov S., “Elementary theories and their constructive models”, Handbook of recursive mathematics. V. 1: Recursive model theory, Stud. Logic and Found. Math., 138, Elsevier, Amsterdam, 1998, 115–165 | DOI | MR | Zbl

[24] Nurtazin A.T., “Silnye i slabye konstruktivizatsii i vychislimye semeistva”, Algebra i logika, 13:3 (1974), 311–323 | MR | Zbl

[25] Harrington L., “Recursively presentable prime models”, J. Symb. Logic, 39 (1974), 305–309 | DOI | MR | Zbl

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

[27] Chisholm J., “Effective model theory vs. recursive model theory”, J. Symb. Logic, 55:3 (1990), 1168–1191 | DOI | MR | Zbl

[28] Goncharov S.S., Schetnye bulevy algebry i razreshimost, Nauch. kn., Novosibirsk, 1996 | MR | Zbl

[29] Goncharov S.S., Ershov Yu.L., Konstruktivnye modeli, Nauch. kn., Novosibirsk, 1999

[30] Goncharov S.S., “Avtoustoichivost prostykh modelei otnositelno silnykh konstruktivizatsii”, Algebra i logika, 48:6 (2009), 729–740 | MR | Zbl

[31] Goncharov S.S., “Ob avtoustoichivosti otnositelno silnykh konstruktivizatsii pochti prostykh modelei”, UMN., 65:5 (2010), 107–142 | DOI | MR | Zbl

[32] Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR

[33] Keisler G., Chen Ch.Ch., Teoriya modelei, Mir, M., 1977 | MR

[34] Maltsev A.I., Algoritmy i rekursivnye funktsii, Nauka, M., 1965 | MR

[35] Palyutin E.A., “Ob algebrakh formul schetno kategorichnykh teorii”, Colloq. Math., 31:2 (1974), 157–159 | Zbl

[36] Goncharov S.S., Nait Dzh., “Vychislimye strukturnye i antistrukturnye teoremy”, Algebra i logika, 41:6 (2002), 639–681 | MR | Zbl

[37] Ershov Yu.L., Problemy razreshimosti i konstruktivnye modeli, Nauka, M., 1980 | MR

[38] McCoy C.F.D., “$\Delta ^0_2$-categoricity in Boolean algebras and linear orderings”, Ann. Pure and Appl. Logic, 119:1–3 (2003), 85–120 | DOI | MR | Zbl

[39] Mak–Koi Ch.F.D., “O $\Delta ^0_3$-kategorichnosti dlya lineinykh poryadkov i bulevykh algebr”, Algebra i logika, 41:5 (2002), 531–552 | MR