## Degrees of categoricity on a cone via $$\eta$$-systems.(English)Zbl 1386.03049

Let $$C_{\mathbf d}=\{\mathbf c:\mathbf c\geq\mathbf d\}$$ be a cone of Turing degrees. A countable structure $$\mathcal A$$ is $$\Delta^0_{\alpha}$$ categorical on the cone $$C_{\mathbf d}$$ if for all $$\mathbf c\geq\mathbf d$$, whenever $$\mathcal B$$ and $$\mathcal C$$ are $$\mathbf c$$-computable copies of $$\mathcal A$$, there exists a $$\Delta^0_{\alpha}(\mathbf c)$$-computable isomorphism between $$\mathcal B$$ and $$\mathcal C$$. Every countable structure is $$\Delta^0_{\alpha}$$ categorical on a cone for some $$\alpha$$.
The first result of the paper (Theorem 1.7) concerns the difficulty of computing isomorphism between two copies of a structure: if $$\alpha$$ is such that a countable structure $$\mathcal A$$ is $$\Delta^0_{\alpha}$$ categorical on a cone, then for every copy $$\mathcal B$$ of $$\mathcal A$$, there is a degree $$\mathbf d$$ that is $$\Sigma^0_{\alpha-1}$$ if $$\alpha$$ is a successor, or $$\Delta^0_{\alpha}(\mathcal B)$$ if $$\alpha$$ is a limit, such that $$\mathbf d$$ is the least degree of an isomorphism between $$\mathcal A$$ and $$\mathcal B$$. A structure $$\mathcal A$$ has degree of categoricity $$\mathbf d$$ relative to $$\mathbf c$$ if $$\mathbf d\geq\mathbf c$$ is the least degree such that there is a $$\mathbf d$$-computable isomorphisms between any two $$\mathbf c$$-computable copies of $$\mathcal A$$. If in addition there exist two $$\mathbf c$$-computable copies of $$\mathcal A$$ such that for every isomorphism $$f$$ between them $$f\oplus\mathbf c\geq_T\mathbf d$$ then $$\mathcal A$$ has strong degree of categoricity $$\mathbf d$$ relative to $$\mathbf c$$. A structure $$\mathcal A$$ has a (strong) degree of categoricity on the cone $$C_{\mathbf d}$$ if for every $$\mathbf c\geq\mathbf d$$, $$\mathcal A$$ has a (strong) degree of categoricity relative to $$\mathbf c$$. It is proved that every $$\Delta^0_2$$ categorical on a cone structure $$\mathcal A$$ has $$\Delta^0_1$$-complete or $$\Delta^0_2$$-complete degree of categoricity on a cone.
A more general Theorem 1.5 states that every countable structure has a strong degree of categoricity on a cone, and this degree of categoricity is $$\Delta^0_{\alpha}$$-complete, where $$\alpha$$ is the least ordinal such that $$\mathcal A$$ is $$\Delta^0_{\alpha}$$ categorical on a cone. The proof uses a modification of A. Montalbán’s $$\eta$$-systems [J. Symb. Log. 79, No. 4, 1315–1335 (2014; Zbl 1353.03050)].

### MSC:

 03D45 Theory of numerations, effectively presented structures 03C57 Computable structure theory, computable model theory 03D28 Other Turing degree structures

Zbl 1353.03050
Full Text:

### References:

  Anderson, B. and Csima, B. F., Degrees that are not degrees of categoricity. Notre Dame Journal of Formal Logic, vol. 57 (2016), no. 3, pp. 389-398. · Zbl 1436.03229  Ash, C. J., Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees. Transactions of the American Mathematical Society, vol. 298 (1986), no. 2, pp. 497-514. doi:10.1090/S0002-9947-1986-0860377-7 · Zbl 0631.03017  Ash, C. J., Stability of recursive structures in arithmetical degrees. Annals of Pure and Applied Logic, vol. 32 (1986), no. 2, pp. 113-135. doi:10.1016/0168-0072(86)90048-5 · Zbl 0631.03016  Ash, C. J., Categoricity in hyperarithmetical degrees. Annals of Pure and Applied Logic, vol. 34 (1987), no. 1, pp. 1-14. doi:10.1016/0168-0072(87)90038-8 · Zbl 0617.03016  Ash, C. J., Labelling systems and r.e. structures. Annals of Pure and Applied Logic, vol. 47 (1990), no. 2, pp. 99-119. doi:10.1016/0168-0072(90)90065-A · Zbl 0712.03021  Ash, C. J. and Knight, J. F., Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland, Amsterdam, 2000. · Zbl 0960.03001  Ash, C. J., Knight, J. F., Manasse, M. S., and Slaman, T. A., Generic copies of countable structures. Annals of Pure and Applied Logic, vol. 42 (1989), no. 3, pp. 195-205. doi:10.1016/0168-0072(89)90015-8 · Zbl 0678.03012  Csima, B. F., Franklin, J. N. Y., and Shore, R. A., Degrees of categoricity and the hyperarithmetic hierarchy. Notre Dame Journal of Formal Logic, vol. 54 (2013), no. 2, pp. 215-231. doi:10.1215/00294527-1960479 · Zbl 1311.03070  Chisholm, J., Effective model theory vs. recursive model theory, this Journal, vol. 55 (1990), no. 3, pp. 1168-1191. · Zbl 0722.03030  Downey, R. G., Kach, A. M., Lempp, S., Lewis-Pye, A. E. M., Montalbán, A., and Turetsky, D. D., The complexity of computable categoricity. Advances in Mathematics, vol. 268 (2015), pp. 423-466. doi:10.1016/j.aim.2014.09.022 · Zbl 1345.03063  Fokina, E., Frolov, A., and Kalimullin, I., Categoricity spectra for rigid structures. Notre Dame Journal of Formal Logic, vol. 57 (2016), no. 1, pp. 45-57. doi:10.1215/00294527-3322017 · Zbl 1359.03030  Fokina, E. B., Kalimullin, I., and Miller, R., Degrees of categoricity of computable structures. Archive for Mathematical Logic, vol. 49 (2010), no. 1, pp. 51-67. doi:10.1007/s00153-009-0160-4 · Zbl 1184.03026  Goncharov, S. S., Autostability and computable families of constructivizations. Algebra and Logic, vol. 14 (1975), no. 6, pp. 392-409 (In Russian). doi:10.1007/BF01668470 · Zbl 0382.03033  Goncharov, S. S., The number of nonautoequivalent constructivizations. Algebra and Logic, vol. 16 (1977), no. 3, pp. 257-282, 377 (In Russian).  Goncharov, S. S. and Dzgoev, V. D., Autostability of models. Algebra and Logic, vol. 19 (1980), no. 1, pp. 28-37 (In Russian). doi:10.1007/BF01669102 · Zbl 0468.03023  Goncharov, S. S., Harizanov, V. S., Knight, J. F., Mccoy, C. F. D., Miller, R. G., and Solomon, R., Enumerations in computable structure theory. Annals of Pure and Applied Logic, vol. 136 (2005), no. 3, pp. 219-246. doi:10.1016/j.apal.2005.02.001 · Zbl 1081.03033  Harizanov, V., Some effects of Ash-Nerode and other decidability conditions on degree spectra. Annals of Pure and Applied Logic, vol. 55 (1991), no. 1, pp. 51-65. doi:10.1016/0168-0072(91)90097-6 · Zbl 0756.03022  Harrison-Trainor, M., Degree spectra of relations on a cone. Memoirs of the American Mathematical Society, to appear. · Zbl 1435.03005  Knight, J. F., Degrees coded in jumps of orderings, this Journal, vol. 51 (1986), no. 4, pp. 1034-1042. · Zbl 0633.03038  Martin, D. A., The axiom of determinateness and reduction principles in the analytical hierarchy. Bulletin of the American Mathematical Society, vol. 74 (1968), pp. 687-689. doi:10.1090/S0002-9904-1968-11995-0 · Zbl 0165.31605  Martin, D. A., Borel determinacy. Annals of Mathematics (2), vol. 102 (1975), no. 2, pp. 363-371. doi:10.2307/1971035 · Zbl 0336.02049  Mccoy, C. F. D., Finite computable dimension does not relativize. Archive for Mathematical Logic, vol. 41 (2002), no. 4, pp. 309-320. doi:10.1007/s001530100113 · Zbl 1023.03040  Miller, R., d-computable categoricity for algebraic fields, this Journal, vol. 74 (2009), no. 4, pp. 1325-1351. · Zbl 1202.03044  Montalbán, A., Priority arguments via true stages, this Journal, vol. 79 (2014), no. 4, pp. 1315-1335.  Montalbán, A., A robuster Scott rank. Proceedings of the American Mathematical Society, vol. 143 (2015), no. 12, pp. 5427-5436. doi:10.1090/proc/12669 · Zbl 1386.03053  Remmel, J. B., Recursively categorical linear orderings. Proceedings of the American Mathematical Society, vol. 83 (1981), no. 2, pp. 387-391. doi:10.1090/S0002-9939-1981-0624937-1 · Zbl 0493.03022  Scott, D., Logic with denumerably long formulas and finite strings of quantifiers, Theory of Models (Proceedings of the 1963 International Symposium at Berkeley), North-Holland, Amsterdam, 1965, pp. 329-341. · Zbl 0166.26003
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.