zbMATH — the first resource for mathematics

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$$.

MSC:
 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:
References:
  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  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  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  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  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  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  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  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  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  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  Ershov, Y. L. and Goncharov, S. S., Constructive Models, Kluwer Academic/Plenum Publishers, New York, 2000. · Zbl 0954.03036  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  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  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  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  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  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  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  Mal’Tsev, A. I., On recursive abelian groups. Soviet Mathematics - Doklady, vol. 32 (1962), pp. 1431-1434. · Zbl 0156.01105  Miller, R., d-computable categoricity for algebraic fields, this Journal, vol. 74 (2009), no. 4, pp. 1325-1351. · Zbl 1202.03044  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.