On categoricity spectra for locally finite graphs. (English. Russian original) Zbl 1534.03042
Sib. Math. J. 62, No. 5, 796-804 (2021); translation from Sib. Mat. Zh. 62, No. 5, 983-994 (2021).
Summary: Under study is the algorithmic complexity of isomorphisms between computable copies of locally finite graphs \(G \) (undirected graphs whose every vertex has finite degree). We obtain the following results: If \(G\) has only finitely many components then \(G\) is \({\mathbf{d}} \)-computably categorical for every Turing degree \({\mathbf{d}}\) from the class \(PA({\mathbf{0}}')\). If \(G\) has infinitely many components then \(G\) is \({\mathbf{0}}''\)-computably categorical. We exhibit a series of examples showing that the obtained bounds are sharp.
MSC:
| 03C57 | Computable structure theory, computable model theory |
| 03C35 | Categoricity and completeness of theories |
Keywords:
computable categoricity; autostability; degree of categoricity; categoricity spectrum; computable model; locally finite graphReferences:
| [1] | Maltsev, AI, On recursive abelian groups, Soviet Math., Dokl., 32, 1431-1434 (1962) · Zbl 0156.01105 |
| [2] | Fokina, EB; Kalimullin, I.; Miller, R., Degrees of categoricity of computable structures, Arch. Math. Logic, 49, 1, 51-67 (2010) · Zbl 1184.03026 · doi:10.1007/s00153-009-0160-4 |
| [3] | Goncharov, SS, Degrees of autostability relative to strong constructivizations, Proc. Steklov Inst. Math., 274, 105-115 (2011) · Zbl 1294.03025 · doi:10.1134/S0081543811060071 |
| [4] | 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 |
| [5] | Csima, BF; Deveau, M.; Harrison-Trainor, M.; Mahmoud, MA, Degrees of categoricity above limit ordinals, Computability, 9, 2, 127-137 (2020) · Zbl 1485.03110 · doi:10.3233/COM-190254 |
| [6] | Miller, R., \( {\mathbf{d}} \)-Computable categoricity for algebraic fields, J. Symb. Log., 74, 4, 1325-1351 (2009) · Zbl 1202.03044 · doi:10.2178/jsl/1254748694 |
| [7] | Bazhenov, NA, Categoricity spectra of computable structures, J. Math. Sci., 256, 1, 34-50 (2021) · Zbl 1485.03105 |
| [8] | Csima B. F., Khoussainov B., and Liu J., “Computable categoricity of graphs with finite components,” in: Logic and Theory of Algorithms: 4th Conf. Computability in Europe, CiE 2008, Springer, Berlin (2008), 139-148. · Zbl 1142.03344 |
| [9] | Bazhenov, NA; Fokina, EB; Rossegger, D.; San Mauro, L., Computable bi-embeddable categoricity, Algebra Logic, 57, 5, 392-396 (2018) · Zbl 1485.03106 · doi:10.1007/s10469-018-9511-8 |
| [10] | Bazhenov, N.; Fokina, E.; Rossegger, D.; San Mauro, L., Degrees of bi-embeddable categoricity, Computability, 10, 1, 1-16 (2021) · Zbl 1535.03197 · doi:10.3233/COM-190289 |
| [11] | Marchuk, MI, Index set of structures with two equivalence relations that are autostable relative to strong constructivizations, Algebra Logic, 55, 4, 306-314 (2016) · Zbl 1402.03050 · doi:10.1007/s10469-016-9400-y |
| [12] | Goncharov, SS; Ershov, YL, Constructive Models (2000), New York, etc.: Kluwer Academic/Plenum, New York, etc. · Zbl 0954.03036 |
| [13] | Ash, CJ; Knight, JF, Computable Structures and the Hyperarithmetical Hierarchy (2000), Amsterdam: Elsevier, Amsterdam · Zbl 0960.03001 |
| [14] | Scott D., “Algebras of sets binumerable in complete extensions of arithmetic,” in: Proc. Sympos. Pure Mathematics, vol. 5, Amer. Math. Soc., Providence (1962), 117-121. · Zbl 0199.02601 |
| [15] | Jockusch, CG; Soare, RI, \( \Pi^0_1 \)-Classes and degrees of theories, Trans. Amer. Math. Soc., 173, 33-56 (1972) · Zbl 0262.02041 |
| [16] | Odifreddi, P., Classical Recursion Theory (1992), Amsterdam: Elsevier, Amsterdam · Zbl 0744.03044 |
| [17] | Simpson S. G., “Degrees of unsolvability: A survey of results,” in: Handbook of Mathematical Logic, Elsevier, Amsterdam (1977), 631-652. |
| [18] | Bazhenov, NA; Kalimullin, IS; Yamaleev, MM, Degrees of categoricity and spectral dimension, J. Symb. Log., 83, 1, 103-116 (2018) · Zbl 1447.03008 · doi:10.1017/jsl.2017.70 |
| [19] | Steiner, RM, Effective algebraicity, Arch. Math. Logic, 52, 1, 91-112 (2013) · Zbl 1300.03021 · doi:10.1007/s00153-012-0308-5 |
| [20] | Bazhenov, NA; Marchuk, MI, Degrees of autostability relative to strong constructivizations of graphs, Sib. Math. J., 59, 4, 566-577 (2018) · Zbl 1469.03102 |
| [21] | Ash, CJ, Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees, Trans. Amer. Math. Soc., 298, 2, 497-514 (1986) · Zbl 0631.03017 · doi:10.1090/S0002-9947-1986-0860377-7 |
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.
