Degrees that are not degrees of categoricity. (English) Zbl 1436.03229

Summary: A computable structure \(\mathcal {A}\) is \(\mathbf {x}\)-computably categorical for some Turing degree \(\mathbf {x}\) if for every computable structure \(\mathcal {B}\cong\mathcal {A}\) there is an isomorphism \(f:\mathcal {B}\to\mathcal {A}\) with \(f\leq_{T}\mathbf {x}\). A degree \(\mathbf {x}\) is a degree of categoricity if there is a computable structure \(\mathcal {A}\) such that \(\mathcal {A}\) is \(\mathbf {x}\)-computably categorical, and for all \(\mathbf {y}\), if \(\mathcal {A}\) is \(\mathbf {y}\)-computably categorical, then \(\mathbf {x}\leq_{T}\mathbf {y}\).
We construct a \(\Sigma^{0}_{2}\) set whose degree is not a degree of categoricity. We also demonstrate a large class of degrees that are not degrees of categoricity by showing that every degree of a set which is 2-generic relative to some perfect tree is not a degree of categoricity. Finally, we prove that every noncomputable hyperimmune-free degree is not a degree of categoricity.


03D45 Theory of numerations, effectively presented structures
03D30 Other degrees and reducibilities in computability and recursion theory
03C57 Computable structure theory, computable model theory
Full Text: DOI arXiv Euclid


[1] Anderson, B. A., “Reals \(n\)-generic relative to some perfect tree,” Journal of Symbolic Logic , vol. 73 (2008), pp. 401-11. · Zbl 1141.03019
[2] Csima, B. F., J. N. Y. Franklin, and R. A. Shore, “Degrees of categoricity and the hyperarithmetic hierarchy,” Notre Dame Journal of Formal Logic , vol. 54 (2013), pp. 215-31. · Zbl 1311.03070
[3] Fokina, E. B., I. Kalimullin, and R. Miller, “Degrees of categoricity of computable structures,” Archive for Mathematical Logic , vol. 49 (2010), pp. 51-67. · Zbl 1184.03026
[4] Harizanov, V. S., “Pure computable model theory,” pp. 3-114 in Handbook of Recursive Mathematics, Vol. 1 , edited by Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, vol. 138 of Studies in Logic and the Foundations of Mathematics , North-Holland, Amsterdam, 1998. · Zbl 0952.03037
[5] Jockusch, C., personal communication cited in Miller, W., and D. A. Martin, “The degrees of hyperimmune sets,” Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 14 (1968), pp. 159-66. · Zbl 0216.29102
[6] Nies, A., Computability and Randomness , vol. 51 of Oxford Logic Guides , Oxford University Press, Oxford, 2009. · Zbl 1169.03034
[7] Soare, R. I., Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets , Perspectives in Mathematical Logic , Springer, Berlin, 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.