Effective categoricity of equivalence Structures

Abstract

An equivalence structure is a set with a single binary relation, satisfying sentences stating that the relation is an equivalence relation. A computable structure A is said to be ${\Delta }_{\alpha }^0$ categorical if for any computable structure B isomorphic to A there is a ${\Delta }_{\alpha }^0$ function witnessing that the two are isomorphic. The present paper gives an exact characterization of ${\Delta }_{\alpha }^0$ equivalence structures where $\alpha =1$ or $\alpha \ge 3$. Extensive results for $\alpha =2$ are also given, and open cases are exhaustively described.

Improved form published