Finite computable dimension and degrees of categoricity. (English) Zbl 06974479

Summary: We first give an example of a rigid structure of computable dimension 2 such that the unique isomorphism between two non-computably isomorphic computable copies has Turing degree strictly below \(0^{\prime\prime}\), and not above \(0^\prime\). This gives a first example of a computable structure with a degree of categoricity that does not belong to an interval of the form \([0^{(\alpha)}, 0^{(\alpha + 1)}]\) for any computable ordinal \(\alpha\). We then extend the technique to produce a rigid structure of computable dimension 3 such that if \(\mathbf{d}_0\), \(\mathbf{d}_1\), and \(\mathbf{d}_2\) are the degrees of isomorphisms between distinct representatives of the three computable equivalence classes, then each \(\mathbf{d}_i < \mathbf{d}_0 \oplus \mathbf{d}_1 \oplus \mathbf{d}_2\). The resulting structure is an example of a structure that has a degree of categoricity, but not strongly.


03D45 Theory of numerations, effectively presented structures
03C57 Computable structure theory, computable model theory
03D80 Applications of computability and recursion theory
03D99 Computability and recursion theory
Full Text: DOI


[1] Anderson, Bernard; Csima, Barbara, Degrees that are not degrees of categoricity, Notre Dame J. Form. Log., 57, 3, 389-398, (2016) · Zbl 1436.03229
[2] Bazhenov, Nikolay A.; Kalimullin, Iskander Sh.; Yamaleev, Mars M., Degrees of categoricity and spectral dimension, J. Symbolic Logic, 83, 1, 103-116, (2018) · Zbl 1447.03008
[3] Cholak, Peter; Goncharov, Sergey; Khoussainov, Bakhadyr; Shore, Richard A., Computably categorical structures and expansions by constants, J. Symbolic Logic, 64, 1, 13-37, (1999) · Zbl 0928.03040
[4] Csima, Barbara F.; Franklin, Johanna N. Y.; Shore, Richard A., Degrees of categoricity and the hyperarithmetic hierarchy, Notre Dame J. Form. Log., 54, 2, 215-231, (2013) · Zbl 1311.03070
[5] Csima, Barbara F.; Harrison-Trainor, Matthew, Degrees of categoricity on a cone via η-systems, J. Symbolic Logic, 82, 1, 325-346, (2017) · Zbl 1386.03049
[6] Fokina, Ekaterina B.; Kalimullin, Iskander; Miller, Russell, Degrees of categoricity of computable structures, Arch. Math. Logic, 49, 1, 51-67, (2010) · Zbl 1184.03026
[7] Franklin, Johanna N. Y., Strength and weakness in computable structure theory, (Day, Adam; Fellows, Michael; Greenberg, Noam; Khoussainov, Bakhadyr; Melnikov, Alexander; Rosamond, Frances, Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, (2017), Springer International Publishing Cham), 302-323 · Zbl 1485.03111
[8] Gončarov, S. S., The problem of the number of nonautoequivalent constructivizations, Algebra Logika, 19, 6, 621-639, (1980), 745
[9] Goncharov, S. S., Limit equivalent constructivizations, (Mathematical Logic and the Theory of Algorithms, Trudy Inst. Mat., vol. 2, (1982), “Nauka” Sibirsk. Otdel Novosibirsk), 4-12
[10] Harizanov, Valentina S., The possible Turing degree of the nonzero member in a two element degree spectrum, Ann. Pure Appl. Logic, 60, 1, 1-30, (1993) · Zbl 0773.03027
[11] Harizanov, Valentina S., Pure computable model theory, (Handbook of Recursive Mathematics, vol. 1, Stud. Logic Found. Math., vol. 138, (1998), North-Holland Amsterdam), 3-114 · Zbl 0952.03037
[12] Hirschfeldt, Denis R., Degree spectra of relations on computable structures, Bull. Symbolic Logic, 6, 2, 197-212, (2000) · Zbl 0968.03038
[13] Hirschfeldt, Denis R., Degree spectra of relations on structures of finite computable dimension, Ann. Pure Appl. Logic, 115, 1-3, 233-277, (2002) · Zbl 1016.03035
[14] Hirschfeldt, Denis R.; Khoussainov, Bakhadyr; Shore, Richard A., A computably categorical structure whose expansion by a constant has infinite computable dimension, J. Symbolic Logic, 68, 4, 1199-1241, (2003) · Zbl 1055.03026
[15] Soare, Robert I., Turing computability, (Theory and Applications of Computability, (2016), Springer-Verlag Berlin) · Zbl 1350.03001
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.