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.

$\endgroup$
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.

$\endgroup$
  • $\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 Jan 6 at 17:36
  • $\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 Jan 6 at 18:54

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.