Degrees of categoricity and spectral dimension. (English) Zbl 1447.03008

Summary: A Turing degree \(\mathbf d\) is the degree of categoricity of a computable structure \(\mathcal S\) if \(\mathbf d\) is the least degree capable of computing isomorphisms among arbitrary computable copies of \(\mathcal S\). A degree \(\mathbf d\) is the strong degree of categoricity of \(\mathcal S\) if \(\mathbf{d}\) is the degree of categoricity of \(\mathcal S\), and there are computable copies \(\mathcal A\) and \(\mathcal B\) of \(\mathcal S\) such that every isomorphism from \(\mathcal A\) onto \(\mathcal B\) computes \(\mathbf d\). In this paper, we build a c.e. degree \(\mathbf d\) and a computable rigid structure \(\mathcal M\) such that \(\mathbf d\) is the degree of categoricity of \(\mathcal M\), but \(\mathbf d\) is not the strong degree of categoricity of \(\mathcal M\). This solves the open problem of E. B. Fokina et al. [Arch. Math. Logic 49, No. 1, 51–67 (2010; Zbl 1184.03026)].
For a computable structure \(\mathcal S\), we introduce the notion of the spectral dimension of \(\mathcal S\), which gives a quantitative characteristic of the degree of categoricity of \(\mathcal S\). We prove that for a nonzero natural number \(N\), there is a computable rigid structure \(\mathcal M\) such that \(0^\prime\) is the degree of categoricity of \(\mathcal M\), and the spectral dimension of \(\mathcal M\) is equal to \(N\).


03D45 Theory of numerations, effectively presented structures
03C57 Computable structure theory, computable model theory
03C35 Categoricity and completeness of theories
03D28 Other Turing degree structures


Zbl 1184.03026
Full Text: DOI


[1] Anderson, B. A. and Csima, B. F., Degrees that are not degrees of categoricity. Notre Dame Journal of Formal Logic, vol. 57 (2016), no. 3, pp. 289-398. · Zbl 1436.03229
[2] Ash, C. J., Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees. Transactions of the American Mathematical Society, vol. 298 (1986), pp. 497-514. doi:10.1090/S0002-9947-1986-0860377-7 · Zbl 0631.03017
[3] Ash, C. J., Stability of recursive structures in arithmetical degrees. Annals of Pure and Applied Logic, vol. 32 (1986), pp. 113-135. doi:10.1016/0168-0072(86)90048-5 · Zbl 0631.03016
[4] Ash, C. J. and Knight, J. F., Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, Elsevier Science B.V., Amsterdam, 2000. · Zbl 0960.03001
[5] Bazhenov, N. A., Degrees of categoricity for superatomic Boolean algebras. Algebra Logic, vol. 52 (2013), no. 3, pp. 179-187. doi:10.1007/s10469-013-9233-x · Zbl 1315.03052
[6] Bazhenov, N. A., \({\rm{\Delta }}_2^0\)-categoricity of Boolean algebras. Journal of Mathematical Sciences, vol. 203 (2014), no. 4, pp. 444-454. doi:10.1007/s10958-014-2148-9
[7] Bazhenov, N. A., Autostability spectra for Boolean algebras. Algebra Logic, vol. 53 (2015), no. 6, pp. 502-505. doi:10.1007/s10469-015-9311-3 · Zbl 1355.03028
[8] Bazhenov, N. A., Kalimullin, I. S., and Yamaleev, M. M., Degrees of categoricity vs. strong degrees of categoricity. Algebra Logic, vol. 55 (2016), no. 2, pp. 173-177. doi:10.1007/s10469-016-9385-6 · Zbl 1402.03066
[9] Csima, B. F., Franklin, J. N. Y., and Shore, R. A., Degrees of categoricity and the hyperarithmetic hierarchy. Notre Dame Journal of Formal Logic, vol. 54 (2013), no. 2, pp. 215-231. doi:10.1215/00294527-1960479 · Zbl 1311.03070
[10] Csima, B. F. and Stephenson, J., Finite computable dimension and degrees of categoricity, to appear. Available at www.math.uwaterloo.ca/∼csima/papers/finitecompdemdegcat.pdf. · Zbl 06974479
[11] Ershov, Y. L. and Goncharov, S. S., Constructive Models, Kluwer Academic/Plenum Publishers, New York, 2000. · Zbl 0954.03036
[12] Fokina, E., Frolov, A., and Kalimullin, I., Categoricity spectra for rigid structures. Notre Dame Journal of Formal Logic, vol. 57 (2016), no. 1, 45-57. doi:10.1215/00294527-3322017 · Zbl 1359.03030
[13] Fokina, E. B., Kalimullin, I., and Miller, R., Degrees of categoricity of computable structures. Archive for Mathematical Logic, vol. 49 (2010), no. 1, pp. 51-67. doi:10.1007/s00153-009-0160-4 · Zbl 1184.03026
[14] Frolov, A. N., Effective categoricity of computable linear orderings. Algebra Logic, vol. 54 (2015), no. 5, pp. 415-417. doi:10.1007/s10469-015-9362-5 · Zbl 1361.03044
[15] Fröhlich, A. and Shepherdson, J. C., Effective procedures in field theory. Philosophical transactions of the Royal Society of London, Series A, vol. 248 (1956), 950, pp. 407-432. doi:10.1098/rsta.1956.0003 · Zbl 0070.03502
[16] Goncharov, S. S., Degrees of autostability relative to strong constructivizations. Proceedings of the Steklov Institute of Mathematics, vol. 274 (2011), pp. 105-115. doi:10.1134/S0081543811060071 · Zbl 1294.03025
[17] Hirschfeldt, D. R., Khoussainov, B., Shore, R. A., and Slinko, A. M., Degree spectra and computable dimensions in algebraic structures. Annals of Pure and Applied Logic, vol. 115 (2002), no. 1-3, pp. 71-113. doi:10.1016/S0168-0072(01)00087-2 · Zbl 1016.03034
[18] Mal’Tsev, A. I., Constructive algebras. I. Russian Mathematical Surveys, vol. 16 (1961), no. 3, pp. 77-129. doi:10.1070/RM1961v016n03ABEH001120 · Zbl 0129.25903
[19] Mal’Tsev, A. I., On recursive abelian groups. Soviet Mathematics - Doklady, vol. 32 (1962), pp. 1431-1434. · Zbl 0156.01105
[20] Miller, R., d-computable categoricity for algebraic fields, this Journal, vol. 74 (2009), no. 4, pp. 1325-1351. · Zbl 1202.03044
[21] Miller, R. and Shlapentokh, A., Computable categoricity for algebraic fields with splitting algorithms. Transactions of the American Mathematical Society, vol. 367 (2015), no. 6, pp. 3955-3980. · Zbl 1375.03052
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.