Computably enumerable sets and quasi-reducibility (Q1295419)

In this very interesting paper the authors investigate the computably enumerable (c.e.) sets under the relation of \(Q\)-reducibility. The following fundamental theorems are proved. 1. There exists a non-computable c.e. set \(A\) and a c.e. set \(B\) with \(A\equiv_T B\) such that \(A\) and \(B\) form a minimal pair in the \(Q\)-degrees. 2. For every c.e. set \(C\not\equiv_Q \emptyset\), there exists a c.e. set \(A\), \(C\nleq_Q A\), which is non-branching in the c.e. \(Q\)-degrees. 3. For every pair of c.e. sets \(B<_QA\), there exists a c.e. set \(C\) with \(B<_Q B\oplus C<_Q A\). This theorem is the affirmative answer to an open question of the reviewer. 4. \(R_Q\) has an undecidable first-order theory.