Journal Article

THE COMPLEXITY OF INDEX SETS OF CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS

ANDREWS, URI, SORBI, ANDREA

2016

Overview

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.

• Publisher: Cambridge University Press,Association for Symbolic Logic, Inc
• Subject: Logic / Mathematics / Philosophy