Classifying equivalence relations in the Ershov hierarchy

Abstract

Computably enumerable equivalence relations (ceers) received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility ${\le }_c$. This gives rise to a rich degree-structure. In this paper, we lift the study of $c$-degrees to the ${\Delta }_2^0$ case. In doing so, we rely on the Ershov hierarchy. For any notation $a$ for a non-zero computable ordinal, we prove several algebraic properties of the degree-structure induced by ${\le }_c$ on the ${\Sigma }_a^{-1}\setminus {\Pi }_a^{-1}$ equivalence relations. A special focus of our work is on the (non)existence of infima and suprema of $c$-degrees.

35 pages