THE COMPLEXITY OF INDEX SETS OF CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
Uri Andrews, Andrea Sorbi · Journal of Symbolic Logic · 2016
Abstract Let $ \le _c $ be computable the reducibility on computably enumerable equivalence relations (or ceers). We show that for every ceerRwith infinitely many equivalence classes, the index sets $\left\{ {i:R_i \le _c R} \right\}$ (withRnonuniversal), $\left\{ {i:R_i \ge _c R} \right\}$ , and $\left\{ {i:R_i \equiv _c R} \right\}$ are ${\rm{\Sigma }}_3^0$ complete, whereas in caseRhas only finitely many equivalence classes, we have that $\left\{ {i:R_i \le _c R} \right\}$ is ${\rm{\Pi }}_2^0$ complete, and $\left\{ {i:R \ge _c R} \right\}$ (withRhaving at least two distinct equivalence classes) is ${\rm{\Sigma }}_2^0$ complete. Next, solving an open problem from [1], we prove that the index set of the effectively inseparable ceers is ${\rm{\Pi }}_4^0$ complete. Finally, we prove that the 1-reducibility preordering on c.e. sets is a ${\rm{\Sigma }}_3^0$ complete preordering relation, a fact that is used to show that the preordering relation $ \le _c $ on ceers is a ${\rm{\Sigma }}_3^0$ complete preordering relation.