Abstract
Defining the degree of categoricity of a computable structure \({\mathcal{M}}\) to be the least degree d for which \({\mathcal{M}}\) is d-computably categorical, we investigate which Turing degrees can be realized as degrees of categoricity. We show that for all n, degrees d.c.e. in and above 0 (n) can be so realized, as can the degree 0 (ω).
Similar content being viewed by others
References
Cholak P., Goncharov S.S., Khoussainov B., Shore R.A.: Computably categorical structures and expansions by constants. J. Symb. Log. 64, 13–37 (1999)
Fröhlich A., Shepherdson J.C.: Effective procedures in field theory. Philos. Trans. R. Soc. Lond. A 248(950), 407–432 (1956)
Goncharov S.S.: Problem of the number of non-self-equivalent constructivizations. Algebra Log. 19, 401–414 (1980)
Goncharov, S.S.: Nonequivalent constructivizations. In: Proceedings of Mathematical Institute of the Siberian Branch Academy of Sciences, Nauka, Novosibirsk (1982)
Goncharov, S.S.: Autostable models and algorithmic dimensions. In: Ershov, Y.L., Goncharov, S.S., Nerode, A., Remmel, J.B. (eds.) Handbook of Recursive Mathematics, vol. 1, pp. 261–287. Elsevier, Amsterdam (1998)
Goncharov S.S., Khoussainov B.: Complexity of categorical theories with computable models. Algebra Log. 43(6), 365–373 (2004)
Goncharov S., Harizanov V., Knight J., McCoy C., Miller R., Solomon R.: Enumerations in computable structure theory. Ann. Pure Appl. Log. 136(3), 219–246 (2005)
Harizanov V.S.: Pure computable model theory. In: Ershov, Y.L., Goncharov, S.S., Nerode, A., Remmel, J.B. (eds) Handbook of Recursive Mathematics, vol. 1, pp. 3–114. Elsevier, Amsterdam (1998)
Harizanov, V.S., Miller, R., Morozov, A.: Automorphism spectra of computable structures (to appear)
Harrison, J.: Doctoral dissertation, Stanford University (1967)
Hirschfeldt D.R., Khoussainov B., Shore R.A., Slinko A.M.: Degree spectra and computable dimensions in algebraic structures. Ann. Pure Appl. Log. 115, 71–113 (2002)
Kreisel G., Shoenfield J., Wang H.: Number theoretic concepts and recursive well-orderings. Arch. Math. Log. Grundl. 5, 42–64 (1960)
Marker D.: Non-Σ n -axiomatizable almost strongly minimal theories. J. Symb. Log. 54, 921–927 (1989)
Miller R.: d-Computable categoricity for algebraic fields. J. Symb. Log. 74(4), 1325–1351 (2009)
Moschovakis Y.N.: Descriptive Set Theory, vol. 100 of Studies in Logic and the Foundations of Mathematics. North-Holland, Amsterdam (1980)
Richter L.J.: Degrees of structures. J. Symb. Log. 46, 723–731 (1981)
Soare R.I.: Recursively Enumerable Sets and Degrees. Springer, New York (1987)
Author information
Authors and Affiliations
Corresponding author
Additional information
E. B. Fokina was partially supported by the Russian Foundation for Basic Research (grant RFBR 08-01-00336) and the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (grant NSh-335.2008.1.). All three authors were supported by binational grant # DMS 0554841 from the National Science Foundation. The main question discussed in this paper was suggested by Sergey Goncharov.
I. Kalimullin was partially supported by the Russian Foundation for Basic Research (grant RFBR 05-01-00605) and RF President grant MK-4314.2008.1.
R. Miller was partially supported by grants numbered 80209-04 12, 67182-00-36, 68470-00 37, 69723-00 38, and 61467-00 39 from The City University of New York PSC-CUNY Research Award Program, and by grant #13397 from the Templeton Foundation.
Rights and permissions
About this article
Cite this article
Fokina, E.B., Kalimullin, I. & Miller, R. Degrees of categoricity of computable structures. Arch. Math. Logic 49, 51–67 (2010). https://doi.org/10.1007/s00153-009-0160-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00153-009-0160-4