Categoricity spectra of computable structures. (English. Russian original) Zbl 1485.03105
J. Math. Sci., New York 256, No. 1, 34-50 (2021); translation from Itogi Nauki Tekh., Ser. Sovrem. Mat. Prilozh., Temat. Obz. 157, 42-58 (2018).
Author’s abstract: 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\). This paper is 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 construct a new series of examples of degrees of categoricity for linear orders.
Reviewer: Andrei S. Morozov (Novosibirsk)
MSC:
| 03C57 | Computable structure theory, computable model theory |
| 03D45 | Theory of numerations, effectively presented structures |
Keywords:
computable categoricity; categoricity spectrum; degree of categoricity; computable structure; linear order; Boolean algebra; decidable categoricity; autostability; autostability relative to strong constructivizations; index setReferences:
| [1] | Alaev, PE, Computably categorical Boolean algebras enriched by ideals and atoms, Ann. Pure Appl. Logic, 163, 5, 485-499 (2012) · Zbl 1247.03057 |
| [2] | Anderson, BA; Csima, BF, Degrees that are not degrees of categoricity, Notre Dame J. Formal Logic, 57, 3, 389-398 (2016) · Zbl 1436.03229 |
| [3] | Ash, CJ, Categoricity in hyperarithmetical degrees, Ann. Pure Appl. Logic, 34, 1, 1-14 (1987) · Zbl 0617.03016 |
| [4] | Ash, CJ, Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees, Trans. Am. Math. Soc., 298, 2, 497-514 (1986) · Zbl 0631.03017 |
| [5] | Ash, CJ, Stability of recursive structures in arithmetical degrees, Ann. Pure Appl. Logic, 32, 2, 113-135 (1986) · Zbl 0631.03016 |
| [6] | C. J. Ash and J. F. Knight, “Computable structures and the hyperarithmetical hierarchy,” in: Stud. Logic Found. Math., 144, Elsevier, Amsterdam (2000). · Zbl 0960.03001 |
| [7] | Ash, CJ; Knight, JF, Pairs of recursive structures, Ann. Pure Appl. Logic, 46, 3, 211-234 (1990) · Zbl 0712.03020 |
| [8] | Ash, C.; Knight, J.; Manasse, M.; Slaman, T., Generic copies of countable structures, Ann. Pure Appl. Logic, 42, 3, 195-205 (1989) · Zbl 0678.03012 |
| [9] | N. A. Bazhenov, “Degrees of categoricity for superatomic Boolean algebras,” Algebra Logic, 52, No. 3, 179-187 (2013). · Zbl 1315.03052 |
| [10] | Bazhenov, NA, \( {\Delta}_2^0 \)-Categoricity of Boolean algebras, J. Math. Sci., 203, 4, 444-454 (2014) |
| [11] | Bazhenov, NA, Hyperarithmetical categoricity of Boolean algebras of type B(ω^α×η), J. Math. Sci., 202, 1, 40-49 (2014) |
| [12] | Bazhenov, NA, Autostability spectra for Boolean algebras, Algebra Logic, 53, 6, 502-505 (2015) · Zbl 1355.03028 |
| [13] | N. A. Bazhenov, “Prime model with no degree of autostability relative to strong constructivizations,” in: Evolving Computability, Lect. Notes Comput. Sci., 9136(A. Beckmann, V. Mitrana, and M. Soskova, eds.), Springer-Verlag, Cham (2015), pp. 117-126. · Zbl 1461.03027 |
| [14] | N. A. Bazhenov, “Degrees of autostability for linear orders and linearly ordered abelian groups,” Algebra Logic, 55, No. 4, 257-273 (2016). · Zbl 1402.03065 |
| [15] | N. A. Bazhenov, “Degrees of autostability relative to strong constructivizations for Boolean algebras,” Algebra Logic, 55, No. 2, 87-102 (2016). · Zbl 1402.03064 |
| [16] | Bazhenov, NA, Categoricity spectra for polymodal algebras, Stud. Log., 104, 6, 1083-1097 (2016) · Zbl 1417.03233 |
| [17] | N. A. Bazhenov, “A note on effective categoricity for linear orderings,” in: Theory and Applications of Models of Computation, Lect. Notes Comput. Sci., 10185 (T. V. Gopal, G. J¨ager, and S. Steila, eds.), Springer-Verlag, Cham (2017), pp. 85-96. · Zbl 1459.03045 |
| [18] | Bazhenov, NA, Effective categoricity for distributive lattices and Heyting algebras, Lobachevskii J. Math., 38, 4, 600-614 (2017) · Zbl 1420.03070 |
| [19] | Bazhenov, NA, Autostability spectra for decidable structures, Math. Struct. Comput. Sci., 28, 3, 392-411 (2018) |
| [20] | Bazhenov, NA; Kalimullin, IS; Yamaleev, MM, Degrees of categoricity vs. strong degrees of categoricity, Algebra Logic, 55, 2, 173-177 (2016) · Zbl 1402.03066 |
| [21] | N. A. Bazhenov and M. M. Yamaleev, “152-161,” in: Unveiling Dynamics and Complexity, Lect. Notes Comput. Sci., 10307 (J. Kari, F. Manea, I. Petre, eds.), Springer-Verlag, Cham (2017). · Zbl 1496.03152 |
| [22] | Calvert, W.; Cenzer, D.; Harizanov, VS; Morozov, A., Effective categoricity of Abelian p-groups, Ann. Pure Appl. Logic, 159, 1-2, 187-197 (2009) · Zbl 1177.03046 |
| [23] | Calvert, W.; Cenzer, D.; Harizanov, VS; Morozov, A., Effective categoricity of equivalence structures, Ann. Pure Appl. Logic, 141, 1-2, 61-78 (2006) · Zbl 1103.03037 |
| [24] | Calvert, W.; Knight, JF, Classification from a computable viewpoint, Bull. Symb. Logic, 12, 2, 191-218 (2006) · Zbl 1123.03024 |
| [25] | D. Cenzer, V. Harizanov, and J. B. Remmel, “Computability-theoretic properties of injection structures,” Algebra Logic, 53, No. 1, 39-69 (2014). · Zbl 1323.03045 |
| [26] | Chang, CC; Keisler, HJ, Model Theory (1973), Amsterdam: North-Holland, Amsterdam · Zbl 0276.02032 |
| [27] | Chisholm, J., Effective model theory vs. recursive model theory, J. Symb. Logic, 55, 3, 1168-1191 (1990) · Zbl 0722.03030 |
| [28] | Chisholm, J.; Fokina, EB; Goncharov, SS; Harizanov, VS; Knight, JF; Quinn, S., Intrinsic bounds on complexity and definability at limit levels, J. Symb. Logic, 74, 3, 1047-1060 (2009) · Zbl 1201.03019 |
| [29] | Csima, BF; Franklin, JNY; Shore, RA, Degrees of categoricity and the hyperarithmetic hierarchy, Notre Dame J. Formal Logic, 54, 2, 215-231 (2013) · Zbl 1311.03070 |
| [30] | Csima, BF; Harrison-Trainor, M., Degrees of categoricity on a cone via η-systems, J. Symb. Logic, 82, 1, 325-346 (2017) · Zbl 1386.03049 |
| [31] | Csima, BF; Stephenson, J., Finite computable dimension and degrees of categoricity, Ann. Pure Appl. Logic, 170, 1, 58-94 (2019) · Zbl 1532.03063 |
| [32] | R. G. Downey, “Computability theory and linear orderings,” in: Handbook of Recursive Mathematics, Vol. 2: Stud. Logic Found. Math., 139 (Yu. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, eds.), Elsevier, Amsterdam (1998), pp. 823-976. · Zbl 0941.03045 |
| [33] | R. G. Downey, A. M. Kach, S. Lempp, A. E. M. Lewis-Pye, A. Montalb´an, and D. D. Turetsky, “The complexity of computable categoricity,” Adv. Math., 268, 423-466 (2015). · Zbl 1345.03063 |
| [34] | Downey, RG; Kach, AM; Lempp, S.; Turetsky, DD, Computable categoricity versus relative computable categoricity, Fund. Math., 221, 2, 129-159 (2013) · Zbl 1320.03070 |
| [35] | Downey, R.; Melnikov, AG, Computable completely decomposable groups, Trans. Am. Math. Soc., 366, 8, 4243-4266 (2014) · Zbl 1341.03056 |
| [36] | Downey, R.; Melnikov, AG, Effectively categorical abelian groups, J. Algebra, 373, 223-248 (2013) · Zbl 1315.03054 |
| [37] | Downey, R.; Melnikov, AG; Ng, KM, Abelian p-groups and the Halting problem, Ann. Pure Appl. Logic, 167, 11, 1123-1138 (2016) · Zbl 1402.03067 |
| [38] | Ershov, YL, Decidability Problems and Constructive Models [in Russian] (1980), Moscow: Nauka, Moscow |
| [39] | Ershov, YL; Goncharov, SS, Constructive Models (2000), New York: Kluwer Academic/Plenum Publishers, New York · Zbl 0954.03036 |
| [40] | Fokina, E.; Frolov, A.; Kalimullin, I., Categoricity spectra for rigid structures, Notre Dame J. Formal Logic, 57, 1, 45-57 (2016) · Zbl 1359.03030 |
| [41] | E. Fokina, V. Harizanov, and A. Melnikov, “Computable model theory,” in: Turing’s Legacy: Developments from Turing’s Ideas in Logic, Lect. Notes Logic, 42 (R. Downey, ed.), Cambridge Univ. Press, Cambridge (2014), pp. 124-194. · Zbl 1341.03002 |
| [42] | Fokina, E.; Harizanov, V.; Turetsky, D., Computability-theoretic categoricity and Scott families, Ann. Pure Appl. Logic, 170, 6, 699-717 (2019) · Zbl 1441.03031 |
| [43] | Fokina, E.; Kalimullin, I.; Miller, R., Degrees of categoricity of computable structures, Arch. Math. Logic, 49, 1, 51-67 (2010) · Zbl 1184.03026 |
| [44] | J. N. Y. Franklin and R. Solomon, “Degrees that are low for isomorphism,” Computability, 3, No. 2, 73-89 (2014). · Zbl 1322.03028 |
| [45] | J. N. Y. Franklin and D. Turetsky, “Lowness for isomorphism and degrees of genericity,” Computability, 7, No. 1, 1-6 (2018). · Zbl 1435.03068 |
| [46] | A. N. Frolov, “Effective categoricity of computable linear orderings,” Algebra Logic, 54, No. 5, 415-417 (2015). · Zbl 1361.03044 |
| [47] | Fröhlich, A.; Shepherdson, JC, Effective procedures in field theory, Phil. Trans. Roy. Soc. London. Ser. A., 248, 950, 407-432 (1956) · Zbl 0070.03502 |
| [48] | S. S. Goncharov, “Autostability and computable families of constructivizations,” Algebra Logic, 14, No. 6, 392-409 (1975). · Zbl 0382.03033 |
| [49] | S. S. Goncharov, “The quantity of nonautoequivalent constructivizations,” Algebra Logic, 16, No. 3, 169-185 (1977). · Zbl 0407.03040 |
| [50] | S. S. Goncharov, “Autostability of models and abelian groups,” Algebra Logic, 19, No. 1, 13-27 (1980). · Zbl 0468.03022 |
| [51] | Goncharov, SS, Limit equivalent constructivizations, Tr. Inst. Mat. Sib. Otdel. Akad. Nauk SSSR, 2, 4-12 (1982) · Zbl 0543.03017 |
| [52] | Goncharov, SS, Countable Boolean Algebras and Decidability (1997), New York: Consultants Bureau, New York · Zbl 0912.03019 |
| [53] | S. S. Goncharov, “Computability and computable models,” in: Mathematical Problems from Applied Logic, Vol. II (D. M. Gabbay, S. S. Goncharov, andM. Zakharyaschev, eds.), Springer-Verlag, New York (2006), pp. 99-216. · Zbl 1143.03017 |
| [54] | Goncharov, SS, Degrees of autostability relative to strong constructivizations, Tr. Mat. Inst. Steklova, 274, 105-115 (2011) · Zbl 1294.03025 |
| [55] | Goncharov, SS; Bazhenov, NA; Marchuk, MI, The index set of Boolean algebras autostable relative to strong constructivizations, Sib. Math. J., 56, 3, 393-404 (2015) · Zbl 1328.03036 |
| [56] | Goncharov, SS; Bazhenov, NA; Marchuk, MI, Index sets of autostable relative to strong constructivizations constructive models for familiar classes, Dokl. Math., 92, 2, 525-527 (2015) · Zbl 1382.03060 |
| [57] | Goncharov, SS; Bazhenov, NA; Marchuk, MI, Index set of linear orderings that are autostable relative to strong constructivizations, J. Math. Sci., 221, 6, 840-848 (2017) · Zbl 1349.03036 |
| [58] | Goncharov, SS; Bazhenov, NA; Marchuk, MI, The index set of the groups autostable relative to strong constructivizations, Sib. Math. J., 58, 1, 72-77 (2017) · Zbl 1420.03071 |
| [59] | S. S. Goncharov and V. D. Dzgoev, “Autostability of models,” Algebra Logic, 19, No. 1, 28-37 (1980). · Zbl 0468.03023 |
| [60] | Goncharov, S.; Harizanov, V.; Knight, J.; McCoy, C.; Miller, R.; Solomon, R., Enumerations in computable structure theory, Ann. Pure Appl. Logic, 136, 3, 219-246 (2005) · Zbl 1081.03033 |
| [61] | Goncharov, SS; Lempp, S.; Solomon, R., The computable dimension of ordered abelian groups, Adv. Math., 175, 1, 102-143 (2003) · Zbl 1031.03058 |
| [62] | S. S. Goncharov and M. I. Marchuk, “Index sets of constructive models of bounded signature that are autostable relative to strong constructivizations,” Algebra Logic, 54, No. 2, 108-126 (2015). · Zbl 1347.03069 |
| [63] | S. S. Goncharov and M. I. Marchuk, “Index sets of constructive models of finite and graph signatures that are autostable relative to strong constructivizations,” Algebra Logic, 54, No. 6, 428-439 (2016). · Zbl 1375.03037 |
| [64] | V. S. Harizanov, “Pure computable model theory,” in: Handbook of Recursive Mathematics, Vol. I, Stud. Logic Found. Math., 138 (Yu. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, eds.), Elsevier, Amsterdam (1998), pp. 3-114. · Zbl 0952.03037 |
| [65] | M. Harrison-Trainor, Degree spectra of relations on a cone, e-print ArXiV 1412.3842. · Zbl 1435.03005 |
| [66] | D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, and A. M. Slinko, “Degree spectra and computable dimensions in algebraic structures,” Ann. Pure Appl. Logic, 115, No. 1-3, 71-113 (2002). · Zbl 1016.03034 |
| [67] | Hirschfeldt, DR; Kramer, K.; Miller, R.; Shlapentokh, A., Categoricity properties for computable algebraic fields, Trans. Am. Math. Soc., 367, 6, 3981-4017 (2015) · Zbl 1347.03082 |
| [68] | Khoussainov, B.; Kowalski, T., Computable isomorphisms of Boolean algebras with operators, Stud. Log., 100, 3, 481-496 (2012) · Zbl 1285.03059 |
| [69] | N. T. Kogabaev, “The theory of projective planes is complete with respect to degree spectra and effective dimensions,” Algebra Logic, 54, No. 5, 387-407 (2015). · Zbl 1375.03038 |
| [70] | N. T. Kogabaev, “Freely generated projective planes with finite computable dimension,” Algebra Logic, 55, No. 6, 461-484 (2017). · Zbl 1420.03073 |
| [71] | O. V. Kudinov, “An autostable 1-decidable model without a computable Scott family of ∃-formulas,” Algebra Logic, 35, No. 4, 255-260 (1996). · Zbl 0972.03038 |
| [72] | Lempp, S.; McCoy, C.; Miller, R.; Solomon, R., Computable categoricity of trees of finite height, J. Symb. Logic, 70, 1, 151-215 (2005) · Zbl 1104.03026 |
| [73] | Levin, O., Computable dimension for ordered fields, Arch. Math. Logic, 55, 3-4, 519-534 (2016) · Zbl 1343.03034 |
| [74] | Mal’tsev, AI, Constructive algebras, I, Russ. Math. Surv., 16, 3, 77-129 (1961) · Zbl 0129.25903 |
| [75] | Mal’tsev, AI, On recursive abelian groups, Sov. Math. Dokl., 3, 1431-1434 (1962) · Zbl 0156.01105 |
| [76] | Mal’tsev, AI, Strongly related models and recursively complete algebras, Sov. Math. Dokl., 3, 987-991 (1962) · Zbl 0132.24702 |
| [77] | M. I. Marchuk, “Index set of structures with two equivalence relations that are autostable relative to strong constructivizations,” Algebra Logic, 55, No. 4, 306-314 (2016). · Zbl 1402.03050 |
| [78] | C. F. D. McCoy, “Partial results in \({\Delta}_3^0 \)-categoricity in linear orderings and Boolean algebras,” Algebra Logic, 41, No. 5, 295-305 (2002). · Zbl 1008.03023 |
| [79] | McCoy, C., \( {\Delta}_2^0 \)-Categoricity in Boolean algebras and linear orderings, Ann. Pure Appl. Logic, 119, 1-3, 85-120 (2003) · Zbl 1016.03036 |
| [80] | Melnikov, AG, Computable abelian groups, Bull. Symb. Logic, 20, 3, 315-356 (2014) · Zbl 1345.03065 |
| [81] | A. G. Melnikov, “Torsion-free abelian groups with optimal Scott families,” J. Math. Logic, 18, No. 1, 1850002 (2018). · Zbl 1522.03175 |
| [82] | Melnikov, AG; Ng, KM, Computable torsion abelian groups, Adv. Math., 325, 864-907 (2018) · Zbl 1470.03018 |
| [83] | Metakides, G.; Nerode, A., Effective content of field theory, Ann. Math. Logic, 17, 3, 289-320 (1979) · Zbl 0469.03028 |
| [84] | Miller, R., d-Computable categoricity for algebraic fields, J. Symb. Logic, 74, 4, 1325-1351 (2009) · Zbl 1202.03044 |
| [85] | Miller, R., The computable dimension of trees of infinite height, J. Symb. Logic, 70, 1, 111-141 (2005) · Zbl 1098.03049 |
| [86] | Miller, R.; Poonen, B.; Schoutens, H.; Shlapentokh, A., A computable functor from graphs to fields (2015) · Zbl 1447.03005 |
| [87] | R. Miller, H. Schoutens, “Computably categorical fields via Fermat’s last theorem,” Computability, 2, No. 1, 51-65 (2013). · Zbl 1408.03029 |
| [88] | Miller, R.; Shlapentokh, A., Computable categoricity for algebraic fields with splitting algorithms, Trans. Am. Math. Soc., 367, 6, 3955-3980 (2015) · Zbl 1375.03052 |
| [89] | A. Montalbán, “Computability theoretic classifications for classes of structures,” in: Proc. Int. Congr. Math. Seoul 2014, Vol. II, Kyung Moon, Seoul (2014), pp. 79-101. · Zbl 1373.03069 |
| [90] | A. T. Nurtazin, “Strong and weak constructivization and computable families,” Algebra Logic, 13, No. 3, 177-184 (1974). · Zbl 0305.02061 |
| [91] | J. B. Remmel, “Recursive isomorphism types of recursive Boolean algebras,” J. Symb. Logic, 46, No. 3, 572-594. · Zbl 0543.03031 |
| [92] | Remmel, JB, Recursively categorical linear orderings, Proc. Am. Math. Soc., 83, 2, 387-391 (1981) · Zbl 0493.03022 |
| [93] | Rogers, H., Theory of Recursive Functions and Effective Computability (1967), New York: McGraw-Hill, New York · Zbl 0183.01401 |
| [94] | J. G. Rosenstein, Linear orderings, Pure Appl. Math., 98, Academic Press, New York etc. (1982). · Zbl 0488.04002 |
| [95] | S. G. Simpson, “Degrees of unsolvability: a survey of results,” in: Handbook of Mathematical Logic. Stud. Logic Found. Math., 90 (J. Barwise, ed.), Elsevier, Amsterdam (1977), pp. 631-652. |
| [96] | R. L. Smith, “Two theorems on autostability in p-groups,” in: Logic year 1979-80, Lect. Notes Math., 859 (M. Lerman, J. H. Schmerl, and R. I. Soare, eds.), Springer-Verlag, Berlin (1981), pp. 302-311. · Zbl 0488.03024 |
| [97] | R. I. Soare, Turing Computability. Theory and Applications, Springer-Verlag, Berlin (2016). · Zbl 1350.03001 |
| [98] | Soare, RI, Recursively Enumerable Sets and Degrees (1987), Berlin: Springer-Verlag, Berlin · Zbl 0623.03042 |
| [99] | D. A. Tussupov, “Isomorphisms and algorithmic properties of structures with two equivalences,” Algebra Logic, 55, No. 1, 50-57 (2016). · Zbl 1420.03107 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
