Degrees of categoricity of computable structures. (English) Zbl 1184.03026

Summary: Defining the degree of categoricity of a computable structure \({\mathcal{M}}\) to be the least degree \(\mathbf d\) for which \({\mathcal{M}}\) is \(\mathbf 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 \(\mathbf 0^{(n)}\) can be so realized, as can the degree \(\mathbf 0^{(\omega)}\).


03C57 Computable structure theory, computable model theory
03C35 Categoricity and completeness of theories
03D28 Other Turing degree structures
Full Text: DOI


[1] Cholak P., Goncharov S.S., Khoussainov B., Shore R.A.: Computably categorical structures and expansions by constants. J. Symb. Log. 64, 13–37 (1999) · Zbl 0928.03040
[2] Fröhlich A., Shepherdson J.C.: Effective procedures in field theory. Philos. Trans. R. Soc. Lond. A 248(950), 407–432 (1956) · Zbl 0070.03502
[3] Goncharov S.S.: Problem of the number of non-self-equivalent constructivizations. Algebra Log. 19, 401–414 (1980) · Zbl 0476.03046
[4] Goncharov, S.S.: Nonequivalent constructivizations. In: Proceedings of Mathematical Institute of the Siberian Branch Academy of Sciences, Nauka, Novosibirsk (1982) · Zbl 0543.03017
[5] 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) · Zbl 0958.03030
[6] Goncharov S.S., Khoussainov B.: Complexity of categorical theories with computable models. Algebra Log. 43(6), 365–373 (2004) · Zbl 1097.03027
[7] 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) · Zbl 1081.03033
[8] 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) · Zbl 0952.03037
[9] Harizanov, V.S., Miller, R., Morozov, A.: Automorphism spectra of computable structures (to appear)
[10] Harrison, J.: Doctoral dissertation, Stanford University (1967)
[11] 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) · Zbl 1016.03034
[12] Kreisel G., Shoenfield J., Wang H.: Number theoretic concepts and recursive well-orderings. Arch. Math. Log. Grundl. 5, 42–64 (1960) · Zbl 0129.00402
[13] Marker D.: Non-{\(\Sigma\)} n -axiomatizable almost strongly minimal theories. J. Symb. Log. 54, 921–927 (1989) · Zbl 0698.03021
[14] Miller R.: d-Computable categoricity for algebraic fields. J. Symb. Log. 74(4), 1325–1351 (2009) · Zbl 1202.03044
[15] Moschovakis Y.N.: Descriptive Set Theory, vol. 100 of Studies in Logic and the Foundations of Mathematics. North-Holland, Amsterdam (1980) · Zbl 0517.03025
[16] Richter L.J.: Degrees of structures. J. Symb. Log. 46, 723–731 (1981) · Zbl 0512.03024
[17] Soare R.I.: Recursively Enumerable Sets and Degrees. Springer, New York (1987) · Zbl 0667.03030
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.