Computably enumerable sets and quasi-reducibility Original Research Article

We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, 〈RQ, ⩽Q〉, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of 〈RQ, ⩽Q〉 is undecidable.