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

### MSC:

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

### References:

  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  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  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  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  Marker, D., “Non $$\Sigma_{n}$$ axiomatizable almost strongly minimal theories,” Journal of Symbolic Logic , vol. 54 (1989), pp. 921-27. · Zbl 0698.03021  Rogers Jr., H., Theory of Recursive Functions and Effective Computability , McGraw-Hill Book Co., New York, 1967. · Zbl 0183.01401  Sacks, G. E., Higher Recursion Theory , Perspectives in Mathematical Logic, Springer, Berlin, 1990. · Zbl 0716.03043  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  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.