×

zbMATH — the first resource for mathematics

The complexity of computable categoricity. (English) Zbl 1345.03063
Summary: We show that the index set complexity of the computably categorical structures is \(\Pi_1^1\)-complete, demonstrating that computable categoricity has no simple syntactic characterization. As a consequence of our proof, we exhibit, for every computable ordinal \(\alpha\), a computable structure that is computably categorical but not relatively \(\operatorname{\Delta}_\alpha^0\)-categorical.

MSC:
03C57 Computable structure theory, computable model theory
03C35 Categoricity and completeness of theories
03D45 Theory of numerations, effectively presented structures
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ash, C. J., Categoricity in hyperarithmetical degrees, Ann. Pure Appl. Logic, 34, 1, 1-14, (1987) · Zbl 0617.03016
[2] Ash, C. J.; Knight, J., Computable structures and the hyperarithmetical hierarchy, Stud. Logic Found. Math., vol. 144, (2000), North-Holland Publishing Co. Amsterdam · Zbl 0960.03001
[3] Chisholm, J.; Fokina, E. B.; Goncharov, S. S.; Harizanov, V. S.; Knight, J. F.; Quinn, S., Intrinsic bounds on complexity and definability at limit levels, J. Symbolic Logic, 74, 3, 1047-1060, (2009) · Zbl 1201.03019
[4] Csima, B. F.; Khoussainov, B.; Liu, J., Computable categoricity of graphs with finite components, (Logic and Theory of Algorithms, Lecture Notes in Comput. Sci., vol. 5028, (2008), Springer Berlin), 139-148 · Zbl 1142.03344
[5] Dehn, M., Über unendliche diskontinuierliche gruppen, Math. Ann., 71, 1, 116-144, (1911) · JFM 42.0508.03
[6] Douni, R.; Khirshvel’d, D.; Khusainov, B., Uniformity in the theory of computable structures, Algebra Logika, 42, 5, 566-593, (2003), 637
[7] Downey, R.; Montalbán, A., The isomorphism problem for torsion-free abelian groups is analytic complete, J. Algebra, 320, 6, 2291-2300, (2008) · Zbl 1156.03042
[8] Downey, R. G.; Hirschfeldt, D. R.; Kach, A. M.; Lempp, S.; Mileti, J. R.; Montalbán, A., Subspaces of computable vector spaces, J. Algebra, 314, 2, 888-894, (2007) · Zbl 1127.03036
[9] Downey, R. G.; Kach, A. M.; Lempp, S.; Turetsky, D. D., Computable categoricity versus relative computable categoricity, Fund. Math., 221, 2, 129-159, (2013), MR3062916 · Zbl 1320.03070
[10] Feferman, S.; Spector, C., Incompleteness along paths in progressions of theories, J. Symbolic Logic, 27, 383-390, (1962) · Zbl 0117.25701
[11] Fröhlich, A.; Shepherdson, J. C., Effective procedures in field theory, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 248, 407-432, (1956) · Zbl 0070.03502
[12] Gončarov, S. S., Selfstability, and computable families of constructivizations, Algebra Logika, 14, 6, 647-680, (1975), 727
[13] Gončarov, S. S., The number of nonautoequivalent constructivizations, Algebra Logika, 16, 3, 257-282, (1977), 377
[14] Gončarov, S. S.; Dzgoev, V. D., Autostability of models, Algebra Logika, 19, 1, 45-58, (1980), 132
[15] Goncharov, S. S., Autostability of models and abelian groups, Algebra Logika, 19, 1, 23-44, (1980), 132 · Zbl 0468.03022
[16] Goncharov, S.; Harizanov, V.; Knight, J.; McCoy, C.; Miller, R.; Solomon, R., Enumerations in computable structure theory, Ann. Pure Appl. Logic, 136, 3, 219-246, (2005) · Zbl 1081.03033
[17] Goncharov, S. S.; Lempp, S.; Solomon, R., The computable dimension of ordered abelian groups, Adv. Math., 175, 1, 102-143, (2003) · Zbl 1031.03058
[18] Hermann, G., Die frage der endlich vielen schritte in der theorie der polynomideale, Math. Ann., 95, 1, 736-788, (1926) · JFM 52.0127.01
[19] La Roche, P. E., Contributions to recursive algebra, (1978), Cornell University Ann Arbor, MI, ProQuest LLC, PhD thesis
[20] Lempp, S.; McCoy, C.; Miller, R.; Solomon, R., Computable categoricity of trees of finite height, J. Symbolic Logic, 70, 1, 151-215, (2005) · Zbl 1104.03026
[21] Mal’cev, A. I., Constructive algebras. I, Uspekhi Mat. Nauk, 16, 3(99), 3-60, (1961)
[22] Mal’cev, A. I., On recursive abelian groups, Dokl. Akad. Nauk SSSR, 146, 1009-1012, (1962)
[23] Miller, R.; Schoutens, H., Computably categorical fields via Fermat’s last theorem, Computability, 2, 1, 51-65, (2013), MR3123253 · Zbl 1408.03029
[24] Nurtazin, A. T., Computable classes and algebraic criteria of autostability, (1974), Math. Inst. SB USSR AS Novosibirsk, PhD thesis
[25] Rabin, M. O., Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc., 95, 341-360, (1960) · Zbl 0156.01201
[26] Smith, R. L., Two theorems on autostability in p-groups, (Logic Year 1979-80, Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, CT, 1979/80, Lecture Notes in Math., vol. 859, (1981), Springer Berlin), 302-311
[27] Soare, R. I., Recursively enumerable sets and degrees: A study of computable functions and computably generated sets, Perspect. Math. Logic, (1987), Springer-Verlag Berlin · Zbl 0623.03042
[28] Soskov, I. N., Intrinsically hyperarithmetical sets, MLQ Math. Log. Q., 42, 4, 469-480, (1996) · Zbl 0859.03016
[29] Turing, A. M., On computable numbers, with an application to the entscheidungsproblem, Proc. Lond. Math. Soc., S2-42, 1, 230, (1936) · JFM 62.1059.03
[30] van der Waerden, B. L., Eine bemerkung über die unzerlegbarkeit von polynomen, Math. Ann., 102, 1, 738-739, (1930) · JFM 56.0825.05
[31] White, W. M., On the complexity of categoricity in computable structures, MLQ Math. Log. Q., 49, 6, 603-614, (2003) · Zbl 1035.03017
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.