7
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ I guess you want that $B$ and $C$ are incomparable? Otherwise, taking $C\geq_T B$ satisfies your conditions. $\endgroup$ May 15, 2018 at 15:42
  • $\begingroup$ Ohh yah, forgot to add that i will do that now. $\endgroup$ May 15, 2018 at 15:43

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks! It's always easier when someone else has already proved the result you want :-) $\endgroup$ May 16, 2018 at 11:23
  • $\begingroup$ I’m unchecking this answer because I've heard from Minzhong Cai that he thinks the result is false so the answer doesn't confuse anyone who comes along. Let me know if that's incorrect. $\endgroup$ Dec 1, 2020 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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