(joint work with Uri Andrews, Joe Miller, Keng Meng Ng, Steffen Lemmp, and Andrea Sorbi)
The theory of c.e. equivalence relations (ceers) has been approached in different ways (for instance: looking for a computable analogue of Borel reducibility, or, as in Ershov's seminal work, considering the theory of numberings). In this talk, we focus on the degree structure P generated by the following reducibility: given two ceers R and S, we say that R is reducible to S if there exists a computable function f s.t. for every x,y, xRy iff f(x)Sf(y).
Our presentation is divided in two parts. Firstly, through an examination of a particular class of ceers, we give a couple of general results on P: we show that P is neither an upper semilattice nor a lower semilattice, and that its first-order theory is undecidable.
Then, we move our attention to universal ceers. We begin with an overview of two classical properties that imply universality (precompletness and e-completness) and we show the failure of Myhill Isomorphism Theorem in this context. Finally, we discuss the interplay between effective inseparability and universality for ceers, showing that every uniformly e.i. ceer is universal.