Analogues of the countable Borel equivalence relations in the setting of computable reducibility

Coskey, Hamkins, and Miller [Computability 1 (2012), pp. 15–38] proposed two possible analogues of the class of countable Borel equivalence relations in the setting of computable reducibility of equivalence relations on the computably enumerable (c.e.) sets. The first is based on effectivizing the Lusin–Novikov theorem while the latter is based on effectivizing the Feldman–Moore theorem. They asked for an analysis of which degrees under computable reducibility are attained under each of these notions. We investigate these two notions, in particular showing that the latter notion has a strict dichotomy theorem: Every such equivalence relation is either equivalent to the relation of equality (=ce) or almost equality (E0ce) between c.e. sets. For the former notion, we show that this is not true, but rather there are both chains and antichains of such equivalence relations on c.e. sets which are between =ce and E0ce. This gives several strong answers to Coskey, Hamkins, and Miller [Question 3.5, Computability 1 (2012), pp. 15–38] showing that in general there is no analogue of the Glimm-Efros dichotomy for equivalence relations on the c.e. sets.