Effective categoricity of equivalence structures (Q2498900)

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\}\).