×

zbMATH — the first resource for mathematics

Effective categoricity of equivalence structures. (English) Zbl 1103.03037
In the paper under review, the authors study effective categoricity of computable equivalence structures. A structure \({\mathcal A}=\{A;E^{{\mathcal A}}\}\) is an equivalence structure, if it consists of a set \(A\) with a binary relation \(E^{{\mathcal A}}\) that is reflexive, symmetric, and transitive. It is proved that such a structure \({\mathcal A}\) is computably categorical if and only if \({\mathcal A}\) has only finitely many finite equivalence classes, or \({\mathcal A}\) has only finitely many infinite classes, bounded character, and at most one finite \(k\) such that there are infinitely many classes of size \(k\). (\({\mathcal A}\) has bounded character if there is some finite \(k\) such that all finite equivalence classes of \({\mathcal A}\) have size at most \(k\)). It is also proved that all computably categorical structures have computably enumerable Scott families of existential formulas. The authors also characterize relatively \(\Delta_2^0\)-categorical equivalence structures and study the complexity of isomorphisms for stuctures \({\mathcal A}\) and \({\mathcal B}\) such that both Fin\(^A\) and Fin\(^B\) are computable, or \(\Delta_2^0\). Here, by definition, \(\text{Fin}^A=\{a:[a]^{{\mathcal A}} \text{ is finite}\}\), and \([a]^{{\mathcal A}}=\{x\in A: xE^{{\mathcal A}}a\}\).

MSC:
03C57 Computable structure theory, computable model theory
PDF BibTeX Cite
Full Text: DOI
References:
[1] Ash, C.J., Categoricity in hyperarithmetical degrees, Annals of pure and applied logic, 34, 1-14, (1987) · Zbl 0617.03016
[2] Ash, C.J.; Knight, J.F., Computable structures and the hyperarithmetical hierarchy, (2000), Elsevier Amsterdam · Zbl 0960.03001
[3] Ash, C.; Knight, J.; Manasse, M.; Slaman, T., Generic copies of countable structures, Annals of pure and applied logic, 42, 195-205, (1989) · Zbl 0678.03012
[4] Chisholm, J., Effective model theory vs. recursive model theory, Journal symbolic logic, 55, 1168-1191, (1990) · Zbl 0722.03030
[5] Cholak, P.; Goncharov, S.; Khoussainov, B.; Shore, R.A., Computably categorical structures and expansions by constants, Journal of symbolic logic, 64, 13-37, (1999) · Zbl 0928.03040
[6] Goncharov, S.S., Autostability and computable families of constructivizations, Algebra and logic, 14, 647-680, (1975), (in Russian), pp. 392-409 (English translation)
[7] Goncharov, S.S., The quantity of nonautoequivalent constructivizations, Algebra and logic, 16, 257-282, (1977), (in Russian), pp. 169-185 (English translation) · Zbl 0407.03040
[8] Goncharov, S.S., Autostability of models and abelian groups, Algebra and logic, 19, 23-44, (1980), (in Russian), pp. 13-27 (English translation) · Zbl 0468.03022
[9] Goncharov, S.S.; Dzgoev, V.D., Autostability of models, Algebra and logic, 19, 45-58, (1980), (in Russian), pp. 28-37 (English translation) · Zbl 0468.03023
[10] Goncharov, S.S.; Harizanov, V.S.; Knight, J.F.; McCoy, C.F.D.; Miller, R.G.; Solomon, R., Enumerations in computable structure theory, Annals of pure and applied logic, 136, 219-246, (2005) · Zbl 1081.03033
[11] Goncharov, S.S.; Harizanov, V.S.; Knight, J.F.; Shore, R.A., \(\prod_1^1\) relations and paths through \(\mathcal{O}\), Journal of symbolic logic, 69, 585-611, (2004) · Zbl 1107.03051
[12] Goncharov, S.; Lempp, S.; Solomon, R., The computable dimension of ordered abelian groups, Advances in mathematics, 175, 102-143, (2003) · Zbl 1031.03058
[13] Khisamiev, N.G., Constructive abelian \(p\)-groups, Siberian advances in mathematics, 2, 68-113, (1992), (English translation) · Zbl 0854.03037
[14] Khoussainov, B.; Nies, A.; Shore, R.A., Computable models of theories with few models, Notre dame journal of formal logic, 38, 165-178, (1997) · Zbl 0891.03013
[15] Khoussainov, B.; Shore, R.A., Computable isomorphisms, degree spectra of relations and Scott families, Annals of pure and applied logic, 93, 153-193, (1998) · Zbl 0927.03072
[16] Kudinov, O.V., An autostable 1-decidable model without a computable Scott family of \(\exists\)-formulas, Algebra and logic, 35, 458-467, (1996), (in Russian), pp. 255-260 (English translation) · Zbl 0972.03038
[17] LaRoche, P., Recursively presented Boolean algebras, Notices AMS, 24, A552-A553, (1977)
[18] Lempp, S.; McCoy, C.; Miller, R.; Solomon, R., Computable categoricity of trees of finite height, Journal of symbolic logic, 70, 151-215, (2005) · Zbl 1104.03026
[19] McCoy, C.F.D., \(\operatorname{\Delta}_2^0\)-categoricity in Boolean algebras and linear orderings, Annals of pure and applied logic, 119, 85-120, (2003) · Zbl 1016.03036
[20] Metakides, G.; Nerode, A., Effective content of field theory, Annals of mathematical logic, 17, 289-320, (1979) · Zbl 0469.03028
[21] Millar, T., Recursive categoricity and persistence, Journal of symbolic logic, 51, 430-434, (1986) · Zbl 0631.03018
[22] Miller, R., The computable dimension of trees of infinite height, Journal of symbolic logic, 70, 111-141, (2005) · Zbl 1098.03049
[23] Nurtazin, A.T., Strong and weak constructivizations and computable families, Algebra and logic, 13, 311-323, (1974), (in Russian), pp. 177-184 (English translation)
[24] Remmel, J.B., Recursively categorical linear orderings, Proceedings of the American mathematical society, 83, 387-391, (1981) · Zbl 0493.03022
[25] Remmel, J.B., Recursive isomorphism types of recursive Boolean algebras, Journal of symbolic logic, 46, 572-594, (1981) · Zbl 0543.03031
[26] Selivanov, V.L., Enumerations of families of general recursive functions, Algebra and logic, 15, 205-226, (1976), (in Russian), pp. 128-141 (English translation)
[27] Smith, R.L., Two theorems on autostability in \(p\)-groups, (), 302-311
[28] Soare, R.I., Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, (1987), Springer-Verlag Berlin · Zbl 0623.03042
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.