Weakly Precomplete Equivalence Relations in the Ershov Hierarchy

详细

We study the computable reducibility ≤_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 \( {\varPi}_a^{-1} \) -universal equivalence relation and a weakly precomplete \( {\varSigma}_a^{-1} \) - universal equivalence relation. We prove that for any \( {\varSigma}_a^{-1} \) equivalence relation E, there is a weakly precomplete \( {\varSigma}_a^{-1} \) equivalence relation F such that E ≤_cF. For finite levels \( {\varSigma}_m^{-1} \) in the Ershov hierarchy at which m = 4k +1 or m = 4k +2, it is shown that there exist infinitely many ≤_c-degrees containing weakly precomplete, proper \( {\varSigma}_m^{-1} \) equivalence relations.