5
$\begingroup$

I feel like there must be a classical result answering this question (or easily modified to do so) but a quick flip through Soare didn't produce anything so rather than waste time I figured I'd just ask.

Given incomplete r.e.sets $C \nleq_T B$ must there exist a low r.e. set $A <_T C$ with $A \nleq_T B$?

I'm guessing the answer is no and somehow you can put together Robinson low splitting with one of the non-splitting/non-bounding theorems to show this but I'm not seeing it right away.

EDIT: Great answer to the original question below (thanks Ted!) but I realized I should have specified that I wanted the set produced uniformly for the application I wanted.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

By Sacks’s splitting theorem, the degree of C is the join of the degrees of two low r.e. sets, both strictly below the degree of C. They can’t both be recursive in B, so at least one of them can serve as A. So, yes, there is such an A.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! But I was actually hoping for a uniform construction of such a set (want to use it for w-REA stuff). Do you know if that's an existing result or should I just go ahead and try to build it? $\endgroup$
    – Peter Gerdes
    Commented Jan 6, 2019 at 17:36
  • 1
    $\begingroup$ Hi Peter. I suspect that you will have to settle the uniform question from first principles. I don't know a quick derivation from results in the literature. $\endgroup$
    – Theodore Slaman
    Commented Jan 6, 2019 at 18:54

You must log in to answer this question.

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