3
$\begingroup$

I’m mostly interested in this is the case where $A, \hat{A}$ are r.e. but the general case seems worth asking too.

Suppose I have sets $A >_T \hat{A}$ with $A' \equiv_T \hat{A}'$. Does this imply that if $C$ is r.e. in $A$ then there is a $\hat{C}$ r.e. in $\hat{A}$ such that $A \oplus C \equiv_T \hat{A} \oplus \hat{C}$?

The following is motivation and can be skipped if it's confusing.

I’m basically wondering if I'm building 2-REA sets whether the jump of the base degree ($A$ or $\hat{A}$ here) completely determine the degrees of the 2-REA sets I can build over that degree (assuming I'm only considering bases comparable to each other) or is it possible to sorta thing out the range of 2-REA degrees that can be built by moving to a smaller base degree.

$\endgroup$

1 Answer 1

2
$\begingroup$

The answer is no. Every properly n-REA set for n < 3 (I believe Peter Cholak and I have shown this fails at 3 but could always fall apart in write-up) can be extended to a properly n+1 REA set by adding a relative r.e. set. Now apply this result to a low r.e. set. You can find that result in a paper by Peter Cholak and Peter Hinman but the result for n=1 was one of the S computability theorists (Shore, Soare, etc) and I don't remember who off the top of my head.

$\endgroup$
0

You must log in to answer this question.

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