On dark computably enumerable equivalence relations (Q1642296)

Ceers (c.e~equivalence relations) on \(\omega\) can be compared by \(\leq_c\), where \(R \leq_c S\) means that for some computable~\(f\), \(\forall x\forall y(xRy\Leftrightarrow f(x)Sf(y))\). A \textsl{dark} equivalence relation is one that is \(\leq_c\)-incomparable with the identity relation. A \textsl{weakly precomplete} equivalence relation~\(R\) is one for which some partial computable \(g\) satisfies \(\forall e[\varphi_e\text{\;total}\Rightarrow(g(e)\!\!\downarrow \&\, \varphi_e(g(e))Rg(e))]\). The main result of this paper is that every dark ceer~\(R\) satisfies \(R <_c S\) for some weakly precomplete dark ceer~\(S\). The authors also provide similarly flavored results for c.e.~preorders that mod out to linear orders.