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.

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! It's always easier when someone else has already proved the result you want :-) $\endgroup$
    – Peter Gerdes
    Commented 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$
    – Peter Gerdes
    Commented Dec 1, 2020 at 4:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .