THE COMPLEXITY OF INDEX SETS OF CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS. (1st December 2016)

• Record Type: Journal Article
• Authors: ANDREWS, URI; SORBI, ANDREA
• Is Part Of: Journal of symbolic logic. Volume 81:Number 4(2016)
• Page Start: 1375
• Page End: 1395
• Publication Date: 2016-12-01
• Subjects: 03D25; computably enumerable equivalence relation, -- computable reducibility on equivalence relations; Logic, Symbolic and mathematical -- Periodicals; 511.3
• DOI: 10.1017/jsl.2016.26
• Languages: English
• ISSNs: 0022-4812

Abstract

Abstract: Let $ \le _c $ be computable the reducibility on computably enumerable equivalence relations (or ceers). We show that for every ceer R with infinitely many equivalence classes, the index sets $\left\{ {i:R_i \le _c R} \right\}$ (with R nonuniversal), $\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 case R has 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\}$ (with R having 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.