Categoricity spectra of computable structures

N. A. Bazhenov

Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University, Tome 157 (2018), pp. 42-58.

Résumé

The categoricity spectrum of a computable structure $S$ is the set of all Turing degrees capable of computing isomorphisms among arbitrary computable presentations of $S$. The degree of categoricity of $S$ is the least degree in the categoricity spectrum of $S$. The paper gives a survey of results on categoricity spectra and degrees of categoricity for computable structures. We focus on the results about degrees of categoricity for linear orders and Boolean algebras. We build a new series of examples of degrees of categoricity for linear orders.

Détail

Keywords: computable categoricity, categoricity spectrum, degree of categoricity, computable structure, linear order, Boolean algebra, decidable categoricity, autostability, autostability relative to strong constructivizations, index set.

Bibliographie

[1] Bazhenov N. A., “O stepenyakh avtoustoichivosti dlya lineinykh poryadkov i lineino uporyadochennykh abelevykh grupp”, Algebra i logika, 55:4 (2016), 393–418 | MR | Zbl

[2] Bazhenov N. A., “O stepenyakh avtoustoichivosti otnositelno silnykh konstruktivizatsii dlya bulevykh algebr”, Algebra i logika, 55:2 (2016), 133–155 | MR | Zbl

[3] Bazhenov N. A., “Spektry avtoustoichivosti bulevykh algebr”, Algebra i logika, 53:6 (2014), 764–769 | MR

[4] Bazhenov N. A., “Stepeni kategorichnosti superatomnykh bulevykh algebr”, Algebra i logika, 52:3, 271–283 | MR | Zbl

[5] Bazhenov N. A., Kalimullin I. Sh., Yamaleev M. M., “O strogikh i nestrogikh stepenyakh kategorichnosti”, Algebra i logika, 55:2 (2016), 257–263 | MR | Zbl

[6] Goncharov S. S., “Avtoustoichivost i vychislimye semeistva konstruktivizatsii”, Algebra i logika, 14:6 (1975), 647–680 | MR | Zbl

[7] Goncharov S. S., “Avtoustoichivost modelei i abelevykh grupp”, Algebra i logika, 19:1 (1980), 23–44 | MR | Zbl

[8] Goncharov S. S., “O chisle neavtoekvivalentnykh konstruktivizatsii”, Algebra i logika, 16:3 (1977), 257–282 | MR | Zbl

[9] Goncharov S. S., “Predelno ekvivalentnye konstruktivizatsii”, Tr. In-ta mat. SO AN SSSR, 2 (1982), 4–12 | MR | Zbl

[10] Goncharov S. S., “Stepeni avtoustoichivosti otnositelno silnykh konstruktivizatsii”, Tr. Mat. in-ta im. V. A. Steklova RAN, 274 (2011), 119–129 | Zbl

[11] Goncharov S. S., Schetnye bulevy algebry i razreshimost, Nauchnaya kniga, Novosibirsk, 1996 | MR

[12] Goncharov S. S., Bazhenov N. A., Marchuk M. I., “Indeksnoe mnozhestvo avtoustoichivykh otnositelno silnykh konstruktivizatsii bulevykh algebr”, Sib. mat. zh., 56:3 (2015), 498–512 | MR | Zbl

[13] Goncharov S. S., Bazhenov N. A., Marchuk M. I., “Indeksnoe mnozhestvo avtoustoichivykh otnositelno silnykh konstruktivizatsii grupp”, Sib. mat. zh., 58:1 (2017), 95–103 | MR | Zbl

[14] Goncharov S. S., Bazhenov N. A., Marchuk M. I., “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei estestvennykh klassov”, Dokl. RAN, 464:1 (2015), 12–14 | DOI | Zbl

[15] Goncharov S. S., Dzgoev V. D., “Avtoustoichivost modelei”, Algebra i logika, 19:1 (1980), 45–58 | MR | Zbl

[16] Goncharov S. S., Ershov Yu. L., Konstruktivnye modeli, Nauchnaya kniga, Novosibirsk, 1999 | MR

[17] Goncharov S. S., Marchuk M. I., “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei konechnoi signatury i signatury grafov”, Algebra i logika, 54:6 (2015), 663–679

[18] Goncharov S. S., Marchuk M. I., “Indeksnye mnozhestva avtoustoichivykh otnositelno silnykh konstruktivizatsii konstruktivnykh modelei ogranichennoi signatury”, Algebra i logika, 54:2 (2015), 163–192 | MR | Zbl

[19] Ershov Yu. L., Problemy razreshimosti i konstruktivnye modeli, Nauka, M., 1980

[20] Keisler G., Chen Ch. Ch., Teoriya modelei, Mir, M., 1977

[21] Kogabaev N. T., “Svobodno porozhdennye proektivnye ploskosti konechnoi vychislimoi razmernosti”, Algebra i logika, 55:6 (2016), 704–737 | MR

[22] Kogabaev N. T., “Teoriya proektivnykh ploskostei polna otnositelno spektrov stepenei i effektivnykh razmernostei”, Algebra i logika, 54:5 (2015), 599–627 | MR | Zbl

[23] Kudinov O. V., “Avtoustoichivaya 1-razreshimaya model bez vychislimogo semeistva Skotta $\exists$-formul”, Algebra i logika, 35:4 (1996), 458–467 | MR | Zbl

[24] 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

[25] Maltsev A. I., “Konstruktivnye algebry”, I, Usp. mat. nauk, 16:3 (1961), 3–60 | MR | Zbl

[26] Maltsev A. I., “O rekursivnykh abelevykh gruppakh”, Dokl. AN SSSR, 146:5, 1009–1012 | MR | Zbl

[27] Maltsev A. I., “Strogo rodstvennye modeli i rekursivno sovershennye algebry”, Dokl. AN SSSR, 145:2 (1962), 276–279 | Zbl

[28] Marchuk M. I., “Indeksnoe mnozhestvo avtoustoichivykh otnositelno silnykh konstruktivizatsii struktur s dvumya otnosheniyami ekvivalentnosti”, Algebra i logika, 55:4, 465–477 | MR | Zbl

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

[30] Soar R. I., Vychislimo perechislimye mnozhestva i stepeni, Kazan. mat. ob-vo, Kazan, 2000

[31] Tusupov D. A., “Izomorfizmy i algoritmicheskie svoistva struktur s dvumya ekvivalentnostyami”, Algebra i logika, 55:1 (2016), 75–86 | MR

[32] Frolov A. N., “Effektivnaya kategorichnost vychislimykh lineinykh poryadkov”, Algebra i logika, 54:5 (2015), 638–642 | MR | Zbl

[33] Tsenzer D., Kharizanov V., Remmel Dzh. B., “Teoretiko vychislitelnye svoistva struktur s vlozheniem”, Algebra i logika, 53:1 (2014), 60–108 | MR

[34] Alaev P. E., “Computably categorical Boolean algebras enriched by ideals and atoms”, Ann. Pure Appl. Logic, 163:5 (2012), 485–499 | DOI | MR | Zbl

[35] Anderson B. A., Csima B. F., “Degrees that are not degrees of categoricity”, Notre Dame J. Formal Logic, 57:3 (2016), 389–398 | MR | Zbl

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

[37] Ash C. J., “Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees”, Trans. Am. Math. Soc., 298:2 (1986), 497–514 | DOI | MR | Zbl

[38] Ash C. J., “Stability of recursive structures in arithmetical degrees”, Ann. Pure Appl. Logic, 32:2 (1986), 113–135 | DOI | MR | Zbl

[39] Ash C. J., Knight J. F., “Computable structures and the hyperarithmetical hierarchy”, Stud. Logic Found. Math., 144 (2000) | MR

[40] Ash C. J., Knight J. F., “Pairs of recursive structures”, Ann. Pure Appl. Logic, 46:3 (1990), 211–234 | DOI | MR | Zbl

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

[42] Bazhenov N. A., “$\Delta^0_2$-Categoricity of Boolean algebras”, J. Math. Sci., 203:4, 444–454 | DOI | MR

[43] Bazhenov N., “A note on effective categoricity for linear orderings”, Theory and Applications of Models of Computation, Lect. Notes Comput. Sci., 10185, eds. Gopal T. V., Jäger G., Steila S., Springer, Cham, 2017, 85–96 | DOI | MR | Zbl

[44] Bazhenov N., “Autostability spectra for decidable structures”, Math. Struct. Comput. Sci., 28:3 (2018), 392–411 | MR

[45] Bazhenov N., “Categoricity spectra for polymodal algebras”, Stud. Log., 104:6 (2016), 1083–1097 | DOI | MR | Zbl

[46] Bazhenov N. A., “Effective categoricity for distributive lattices and Heyting algebras”, Lobachevskii J. Math., 38:4 (2017), 600–614 | DOI | MR | Zbl

[47] Bazhenov N. A., “Hyperarithmetical categoricity of Boolean algebras of type $B(\omega^{\alpha} \times \eta)$”, J. Math. Sci., 202:1 (2014), 40–49 | DOI | MR

[48] Bazhenov N., “Prime model with no degree of autostability relative to strong constructivizations”, Evolving Computability, Lect. Notes Comput. Sci., 9136, eds. Beckmann A., Mitrana V., Soskova M., Springer, Cham, 2015, 117–126 | DOI | MR | Zbl

[49] Bazhenov N. A., Yamaleev M. M., “Degrees of categoricity of rigid structures”, Unveiling Dynamics and Complexity, Lect. Notes Comput. Sci., 10307, eds. Kari J., Manea F., Petre I., Springer, Cham, 2017 | MR

[50] Calvert W., Cenzer D., Harizanov V. S., Morozov A., “Effective categoricity of Abelian $p$-groups”, Ann. Pure Appl. Logic, 159:1-2 (2009), 187–197 | DOI | MR | Zbl

[51] Calvert W., Cenzer D., Harizanov V. S., Morozov A., “Effective categoricity of equivalence structures”, Ann. Pure Appl. Logic, 141:1-2 (2006), 61–78 | DOI | MR | Zbl

[52] Calvert W., Knight J. F., “Classification from a computable viewpoint”, Bull. Symb. Logic, 12:2 (2006), 191–218 | DOI | MR | Zbl

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

[54] 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

[55] Csima B. F., Franklin J. N. Y., Shore R. A., “Degrees of categoricity and the hyperarithmetic hierarchy”, Notre Dame J. Formal Logic, 54:2 (2013), 215–231 | DOI | MR | Zbl

[56] Csima B. F., Harrison-Trainor M., “Degrees of categoricity on a cone via $\eta$-systems”, J. Symb. Logic, 82:1 (2017), 325–346 | DOI | MR | Zbl

[57] Csima B. F., Stephenson J., in press http://www.math.uwaterloo.ca/<nobr>$\sim$</nobr>csima/papers/finitecompdemdegcat.pdf | MR

[58] Downey R. G., “Computability theory and linear orderings”, Handbook of Recursive Mathematics, Elsevier, Amsterdam, 1998, 823–976 | MR | Zbl

[59] Downey R. G., Kach A. M., Lempp S., Lewis-Pye A. E. M., Montalbán A., Turetsky D. D., “The complexity of computable categoricity”, Adv. Math., 268 (2015), 423–466 | DOI | MR | Zbl

[60] Downey R. G., Kach A. M., Lempp S., Turetsky D. D., “Computable categoricity versus relative computable categoricity”, Fund. Math., 221:2 (2013), 129–159 | DOI | MR | Zbl

[61] Downey R., Melnikov A. G., “Computable completely decomposable groups”, Trans. Am. Math. Soc., 366:8 (2014), 4243–4266 | DOI | MR | Zbl

[62] Downey R., Melnikov A. G., “Effectively categorical abelian groups”, J. Algebra, 373 (2013), 223–248 | DOI | MR | Zbl

[63] Downey R., Melnikov A. G., Ng K. M., “Abelian $p$-groups and the Halting problem”, Ann. Pure Appl. Logic, 167:11 (2016), 1123–1138 | DOI | MR | Zbl

[64] Fokina E., Frolov A., Kalimullin I., “Categoricity spectra for rigid structures”, Notre Dame J. Formal Logic, 57:1 (2016), 45–57 | DOI | MR | Zbl

[65] Fokina E. B., Harizanov V., Melnikov A., “Computable model theory”, Turing's legacy: Developments from Turing's ideas in logic, Lect. Notes Logic, 42, ed. Downey R., Cambridge Univ. Press, Cambridge, 2014, 124–194 | MR

[66] Fokina E., Harizanov V., Turetsky D., “Computability-theoretic categoricity and Scott families”, Ann. Pure Appl. Logic, 170:6 (2019), 699-717 | DOI | MR | Zbl

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

[68] Franklin J. N. Y., Solomon R., “Degrees that are low for isomorphism”, Computability, 3:2 (2014), 73–89 | DOI | MR | Zbl

[69] Franklin J. N. Y., Turetsky D., “Lowness for isomorphism and degrees of genericity”, Computability, 7:1 (2018), 1–6 | MR | Zbl

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

[71] Goncharov S. S., “Computability and computable models”, Mathematical problems from applied logic, v. II, eds. Gabbay D. M., Goncharov S. S., Zakharyaschev M., Springer, New York, 2006, 99–216 | MR

[72] Goncharov S. S., Bazhenov N. A., Marchuk M. I., “Index set of linear orderings that are autostable relative to strong constructivizations”, J. Math. Sci., 221:6 (2017), 840–848 | DOI | MR

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

[74] Goncharov S. S., Lempp S., Solomon R., “The computable dimension of ordered abelian groups”, Adv. Math., 175:1 (2003), 102–143 | DOI | MR | Zbl

[75] Harizanov V. S., “Pure computable model theory”, Handbook of recursive mathematics, v. I, Stud. Logic Found. Math., 138, eds. Ershov Yu. L., Goncharov S. S., Nerode A., Remmel J. B., Elsevier, Amsterdam, 1998, 3–114 | DOI | MR | Zbl

[76] Harrison-Trainor M., Degree spectra of relations on a cone, arXiv: 1412.3842 [math.LO] | MR

[77] Hirschfeldt D. R., Khoussainov B., Shore R. A., Slinko A. M., “Degree spectra and computable dimensions in algebraic structures”, Ann. Pure Appl. Logic, 115:1-3 (2002), 71–113 | DOI | MR | Zbl

[78] Hirschfeldt D. R., Kramer K., Miller R., Shlapentokh A., “Categoricity properties for computable algebraic fields”, Trans. Am. Math. Soc., 367:6 (2015), 3981–4017 | DOI | MR | Zbl

[79] Khoussainov B., Kowalski T., “Computable isomorphisms of Boolean algebras with operators”, Stud. Log., 100:3 (2012), 481–496 | DOI | MR | Zbl

[80] Lempp S., McCoy C., Miller R., Solomon R., “Computable categoricity of trees of finite height”, J. Symb. Logic, 70:1 (2005), 151–215 | DOI | MR | Zbl

[81] Levin O., “Computable dimension for ordered fields”, Arch. Math. Logic, 55:3-4 (2016), 519–534 | DOI | MR | Zbl

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

[83] Melnikov A. G., “Computable abelian groups”, Bull. Symb. Logic, 20:3 (2014), 315–356 | DOI | MR | Zbl

[84] Melnikov A. G., “Torsion-free abelian groups with optimal Scott families”, J. Math. Logic, 18:1 (2018), 1850002 | MR | Zbl

[85] Melnikov A. G., Ng K. M., “Computable torsion abelian groups”, Adv. Math., 325 (2018), 864–907 | DOI | MR | Zbl

[86] Metakides G., Nerode A., “Effective content of field theory”, Ann. Math. Logic, 17:3 (1979), 289–320 | DOI | MR | Zbl

[87] Miller R., “$\mathbf{d}$-Computable categoricity for algebraic fields”, J. Symb. Logic, 74:4 (2009), 1325–1351 | DOI | MR | Zbl

[88] Miller R., “The computable dimension of trees of infinite height”, J. Symb. Logic, 70:1 (2005), 111–141 | DOI | MR | Zbl

[89] Miller R., Poonen B., Schoutens H., Shlapentokh A., A computable functor from graphs to fields, arXiv: 1510.07322 [math.LO] | MR

[90] Miller R., Schoutens H., “Computably categorical fields via Fermat's last theorem”, Computability, 2:1 (2013), 51–65 | DOI | MR | Zbl

[91] Miller R., Shlapentokh A., “Computable categoricity for algebraic fields with splitting algorithms”, Trans. Am. Math. Soc., 367:6 (2015), 3955–3980 | DOI | MR | Zbl

[92] Montalbán A., “Computability theoretic classifications for classes of structures”, Proc. Int. Congr. Math. Seoul 2014, v. II, Kyung Moon, Seoul, 2014, 79–101 | MR | Zbl

[93] Remmel J. B., “Recursive isomorphism types of recursive Boolean algebras”, J. Symb. Logic, 46:3, 572–594 | DOI | MR | Zbl

[94] Remmel J. B., “Recursively categorical linear orderings”, Proc. Am. Math. Soc., 83:2 (1981), 387–391 | DOI | MR | Zbl

[95] Rosenstein J. G., Linear orderings, Academic Press, New York, 1982 | MR | Zbl

[96] Simpson S. G., “Degrees of unsolvability: a survey of results”, Handbook of Mathematical Logic. Stud. Logic Found. Math., Elsevier, Amsterdam, 1977, 631–652 | DOI | MR

[97] Smith R. L., “Two theorems on autostability in $p$-groups”, Logic year 1979–80, Lect. Notes Math., 859, eds. Lerman M., Schmerl J. H., Soare R. I., Springer-Verlag, Berlin, 1981, 302–311 | DOI | MR

[98] Soare R. I., Turing computability. Theory and applications, Springer, Berlin, 2016 | MR | Zbl