# 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
Full Text:
##### References:
  Ash, C.J., Categoricity in hyperarithmetical degrees, Annals of pure and applied logic, 34, 1-14, (1987) · Zbl 0617.03016  Ash, C.J.; Knight, J.F., Computable structures and the hyperarithmetical hierarchy, (2000), Elsevier Amsterdam · Zbl 0960.03001  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  Chisholm, J., Effective model theory vs. recursive model theory, Journal symbolic logic, 55, 1168-1191, (1990) · Zbl 0722.03030  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  Goncharov, S.S., Autostability and computable families of constructivizations, Algebra and logic, 14, 647-680, (1975), (in Russian), pp. 392-409 (English translation)  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  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  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  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  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  Goncharov, S.; Lempp, S.; Solomon, R., The computable dimension of ordered abelian groups, Advances in mathematics, 175, 102-143, (2003) · Zbl 1031.03058  Khisamiev, N.G., Constructive abelian $$p$$-groups, Siberian advances in mathematics, 2, 68-113, (1992), (English translation) · Zbl 0854.03037  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  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  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  LaRoche, P., Recursively presented Boolean algebras, Notices AMS, 24, A552-A553, (1977)  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  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  Metakides, G.; Nerode, A., Effective content of field theory, Annals of mathematical logic, 17, 289-320, (1979) · Zbl 0469.03028  Millar, T., Recursive categoricity and persistence, Journal of symbolic logic, 51, 430-434, (1986) · Zbl 0631.03018  Miller, R., The computable dimension of trees of infinite height, Journal of symbolic logic, 70, 111-141, (2005) · Zbl 1098.03049  Nurtazin, A.T., Strong and weak constructivizations and computable families, Algebra and logic, 13, 311-323, (1974), (in Russian), pp. 177-184 (English translation)  Remmel, J.B., Recursively categorical linear orderings, Proceedings of the American mathematical society, 83, 387-391, (1981) · Zbl 0493.03022  Remmel, J.B., Recursive isomorphism types of recursive Boolean algebras, Journal of symbolic logic, 46, 572-594, (1981) · Zbl 0543.03031  Selivanov, V.L., Enumerations of families of general recursive functions, Algebra and logic, 15, 205-226, (1976), (in Russian), pp. 128-141 (English translation)  Smith, R.L., Two theorems on autostability in $$p$$-groups, (), 302-311  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.