Are there r.e. sets $B >_T 0$ and $C >_T 0$, $C \not\geq_T B$ such that for all r.e. $W \leq_T B$ either $W \leq_T 0$ or $C \oplus W \geq_T B$. The explanation for the title is because one can think of this as saying that there is a gap between $0$ and $B$ in the r.e. degrees join $C$.

I've been hitting my head against this problem for awhile. Originally I thought I had a construction of r.e. degrees with the following property but now I think it's impossible and worry I'm missing something dumb so before I waste more time trying to decide the question one way or another I figured I should find out if I'm missing anything dumb.

Note that it's easy to see that if $B,C$ satisfy then $B$ and $C$ are a minimal pair. Now the initial temptation is to try and use a proof something along the lines of Sack's density theorem for r.e. degrees but one quickly runs into problems since trying to restrain $W$ to ensure $\phi_i(C \oplus W) \neq B$ might impose unbounded restraint (though with finite lim inf) but since $B$ can't compute the stages at which elements enter $C$ to disrupt $\phi_i(C \oplus W)$ one quickly runs into a conflict between the requirement that $W \leq_T B$ and the attempt to ensure $C \oplus W \not\geq_T B$.

Indeed, I can show there is no uniform solution in the following sense. Given a finite lits $i_0\ldots i_n$ of indexes I can uniformly build $C, B$ such that if $W = \phi_{i_j}(B)$ then $W \leq_T 0$ or $C \oplus W \geq_T B$.

Anyway, before I waste any more time trying to decide this question I want to make sure I'm not missing anything obvious.

  • 1
    I guess you want that $B$ and $C$ are incomparable? Otherwise, taking $C\geq_T B$ satisfies your conditions. – Joel David Hamkins May 15 at 15:42
  • Ohh yah, forgot to add that i will do that now. – Peter Gerdes May 15 at 15:43
up vote 6 down vote accepted

You could check barmpalias, cai, lempp and slaman. It shows that there is a pair of the sort that you asked about.

As far as I know, realizing the fully symmetric condition is open.

  • Thanks! It's always easier when someone else has already proved the result you want :-) – Peter Gerdes May 16 at 11:23

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.