5
$\begingroup$

Remember, that an incomplete r.e. set $A$ is cuppable if there is an incomplete r.e. set $B$ such that $A\oplus B \equiv_T 0'$. It's relatively easy to build a low cuppable set but my question is whether for every cuppable set $A$ there is a low r.e. set $B$ such that $A \oplus B \equiv 0'$

I'm pretty sure this must be false (or at least unsolved but I'm betting false) or people wouldn't have had to prove results like the ZBC theorem (one can think of this as the claim that if S is r.e. in 0' then there is an r.e. set A with $A' \equiv 0' \oplus S$ and a $A$ r.e. set $B$ which is low relative to $A$ and cups to $A'$) but maybe someone can point me to a proof.

Note that I'm asking about cupping and capping in R (set of re degrees here) not in D to clarify whats going on with the equivalence claim.

Also, the link with ZBC theorem results was mistaken as just because $0' \oplus S \equiv_T B'$ doesn't guarantee that S itself is re in B. Hence, you can't use low-cuppability to show the ZBC theorem.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ It is in Soare’s book. Low cuppability is equivalent to prompt simplity. $\endgroup$
    – 喻 良
    Commented Oct 22, 2021 at 9:33

1 Answer 1

Reset to default
3
$\begingroup$

It seems that a short comment is not sufficient.

The answer is negative. I.e. there is a cuppable r.e. set which is no low cuppable.

By the results from Soare's book, low cuppability is equivalent to prompt simplicity which is equivalent to noncappbability.

Now the fact is that there is an r.e. degree which is both cappable and cuppable. The result was proved by Harrington in 1970's in an unpublished handwritten notes. Yang and I have an improvement of this by showing that there is a cappable degree which does not belong to the ideal generated by the union of nonbounding and noncuppable degrees (see https://www.jstor.org/stable/pdf/27588357.pdf?refreqid=excelsior%3Aa9865b098fcf6a982c2dfeeb4155a184).

Certainly you may find earlier published papers that imply the result.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Wait, but then the claim comes out false. For, Soare proves that low cuppable is equivalent to PS which is equivalent to Non-cappable. So pick an r.e. set that both cups and caps. If that set was low-cuppable then it would be non-cappable. Contradiction. I assumed you were saying that because low-cuppability is equivalent to PS the claim was true (hence the statement about equiv) but maybe I misread what you were saying. $\endgroup$
    – Peter Gerdes
    Commented Nov 22, 2021 at 9:17
  • 1
    $\begingroup$ Now I see why my comments are confusing. I just made it clearer. $\endgroup$
    – 喻 良
    Commented Nov 23, 2021 at 1:53
  • 1
    $\begingroup$ Ok, yah sorry for being so dense but I was reading your answer as saying the conclusion was positive and then we kept talking past each other because of that initial confusion. Well that and getting confused about my theorems :-) $\endgroup$
    – Peter Gerdes
    Commented Nov 25, 2021 at 13:41

You must log in to answer this question.

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