Abstract:
We study the computable reducibility $\leq_c$ for equivalence relations
in the Ershov hierarchy. For an arbitrary notation $a$ for a nonzero
computable ordinal, it is stated that there exist a
$\Pi^{-1}_a$-universal
equivalence relation and a weakly precomplete
$\Sigma^{-1}_a$-universal
equivalence relation. We prove that for any
$\Sigma^{-1}_a$ equivalence relation
$E$, there is a weakly precomplete
$\Sigma^{-1}_a$ equivalence relation
$F$ such
that $E\leq_c F$.
For finite levels $\Sigma^{-1}_m$ in the Ershov hierarchy at which
$m=4k+1$
or $m=4k+2$, it is shown that there exist infinitely many
$\leq_c$-degrees containing weakly precomplete, proper $\Sigma^{-1}_m$
equivalence relations.