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 $Δ^0_α$ categorical if for any computable structure B isomorphic to A there is a $Δ^0_α$ function witnessing that the two are isomorphic. The present paper gives an exact characterization of $Δ^0_α$ equivalence structures where $α= 1$ or $α\geq 3$. Extensive results for $α= 2$ are also given, and open cases are exhaustively described.

Improved form published