We investigate effective categoricity of computable equivalence structures . We show that is computably categorical if and only if has only finitely many finite equivalence classes, or has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. We also prove that all computably categorical structures are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. Since all computable equivalence structures are relatively categorical, (...) we further investigate when they are categorical. We also obtain results on the index sets of computable equivalence structures. (shrink)

We investigate effective categoricity of computable Abelian p-groups . We prove that all computably categorical Abelian p-groups are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. We investigate which computable Abelian p-groups are categorical and relatively categorical.

We study the relationship between algebraic structures and their inverse semigroups of partial automorphisms. We consider a variety of classes of natural structures including equivalence structures, orderings, Boolean algebras, and relatively complemented distributive lattices. For certain subsemigroups of these inverse semigroups, isomorphism of the subsemigroups yields isomorphism of the underlying structures. We also prove that for some classes of computable structures, we can reconstruct a computable structure, up to computable isomorphism, from the isomorphism type of its inverse semigroup of computable (...) partial automorphisms. (shrink)

We construct a computable vector space with the trivial computable automorphism group, but with the dependence relations as complicated as possible, measured by their Turing degrees. As a corollary, we answer a question asked by A.S. Morozov in [Rigid constructive modules, Algebra and Logic, 28 570–583 ; 379–387 ].

We establish that the isomorphism problem for the classes of computable nilpotent rings, distributive lattices, nilpotent groups, and nilpotent semigroups is \-complete, which is as complicated as possible. The method we use is based on uniform effective interpretations of computable binary relations into computable structures from the corresponding algebraic classes.

In [5] it has been shown that for first-order definability over the reals there exists an effective procedure which by a finite formula with equality defining an open set produces a finite formula without equality that defines the same set. In this paper we prove that there exists no such procedure for Σ-definability over the reals. We also show that there exists even no uniform effective transformation of the definitions of Σ-definable sets into new definitions of Σ-definable sets in such (...) a way that the results will define open sets, and if a definition defines an open set, then the result of this transformation will define the same set. These results highlight the important differences between Σ-definability with equality and Σ-definability without equality. (shrink)