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:

 [1] 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 [2] 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 [3] 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 [4] 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 [5] 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 [6] 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 [7] 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 [8] 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 [9] Chisholm, J., Effective model theory vs. recursive model theory, this Journal, vol. 55 (1990), no. 3, pp. 1168-1191. · Zbl 0722.03030 [10] 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 [11] 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 [12] 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 [13] 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 [14] Goncharov, S. S., The number of nonautoequivalent constructivizations. Algebra and Logic, vol. 16 (1977), no. 3, pp. 257-282, 377 (In Russian). [15] 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 [16] 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 [17] 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 [18] Harrison-Trainor, M., Degree spectra of relations on a cone. Memoirs of the American Mathematical Society, to appear. · Zbl 1435.03005 [19] Knight, J. F., Degrees coded in jumps of orderings, this Journal, vol. 51 (1986), no. 4, pp. 1034-1042. · Zbl 0633.03038 [20] 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 [21] Martin, D. A., Borel determinacy. Annals of Mathematics (2), vol. 102 (1975), no. 2, pp. 363-371. doi:10.2307/1971035 · Zbl 0336.02049 [22] 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 [23] Miller, R., d-computable categoricity for algebraic fields, this Journal, vol. 74 (2009), no. 4, pp. 1325-1351. · Zbl 1202.03044 [24] Montalbán, A., Priority arguments via true stages, this Journal, vol. 79 (2014), no. 4, pp. 1315-1335. [25] 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 [26] 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 [27] 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.