Degrees of categoricity and the hyperarithmetic hierarchy. (English) Zbl 1311.03070

Let \(\mathbf d\) be a Turing degree. A computable structure is \(\mathbf d\)-computably categorical if any of its computable isomorphic copies is isomorphic to it via a \(\mathbf d\)-computable isomorphism. If there is a least degree with this property, then this degree is called the degree of categoricity of this structure. A degree is called a degree of categoricity if it is the degree of categoricity for some computable structure. If \(\mathbf d\) is a degree of categoricity with the property that there are isomorphic computable structures \({\mathcal A}_0\) and \({\mathcal A}_1\) for which \(\mathbf d\) is the degree of categoricity and every isomorphism from \({\mathcal A}_0\) onto \({\mathcal A}_1\) computes \(\mathbf d\), then \(\mathbf d\) is called strong degree of categoricity.
The authors prove the following results:
1) for any computable ordinal \(\alpha\), \({\mathbf 0}^{(\alpha)}\) is the strong degree of categoricity for some computable structure;
2) if in addition \(\alpha\) is a successor ordinal, then any degree \(2\)-c.e. in and above \({\mathbf 0}^{(\alpha)}\) is a strong degree of categoricity;
3) every degree of categoricity is hyperarithmetic;
4) the set of codes of all structures having a degree of categoricity is \(\Pi_1^1\)-complete.


03D45 Theory of numerations, effectively presented structures
03D28 Other Turing degree structures
Full Text: DOI Euclid


[1] Ash, C. J., and J. Knight, Computable Structures and the Hyperarithmetical Hierarchy , vol. 144 of Studies in Logic and the Foundations of Mathematics , North-Holland, Amsterdam, 2000. · Zbl 0960.03001
[2] 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
[3] Harizanov, V. S., “Pure computable model theory,” pp. 3-114 in Handbook of Recursive Mathematics, Vol. 1 , vol. 138 of Studies in Logic and the Foundations of Mathematics , North-Holland, Amsterdam, 1998. · Zbl 0952.03037
[4] Hirschfeldt, D. R., and W. M. White, “Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures,” Notre Dame Journal of Formal Logic , vol. 43 (2002), pp. 51-64. · Zbl 1048.03035
[5] Marker, D., “Non \(\Sigma_{n}\) axiomatizable almost strongly minimal theories,” Journal of Symbolic Logic , vol. 54 (1989), pp. 921-27. · Zbl 0698.03021
[6] Rogers Jr., H., Theory of Recursive Functions and Effective Computability , McGraw-Hill Book Co., New York, 1967. · Zbl 0183.01401
[7] Sacks, G. E., Higher Recursion Theory , Perspectives in Mathematical Logic, Springer, Berlin, 1990. · Zbl 0716.03043
[8] 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
[9] White, W. M., Characterizations for Computable Structures , Ph.D. dissertation, Cornell University, Ithaca, N.Y., 2000.
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.