Skip to main content
Gave spiffier title
Source Link

Join Density in R.E. Degrees: Are there r.e. B, C with all r.e. X below B computable or C join X computes B

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.

R.E. Degrees B, C with all r.e. X below B computable or C join X computes B

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

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.

Join Density in R.E. Degrees: Are there r.e. B, C with all r.e. X below B computable or C join X computes B

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.

forgot part about C not being above B
Source Link

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

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.

Are there r.e. sets $B >_T 0$ and $C >_T 0$ such that for all r.e. $W \leq_T B$ either $W \leq_T 0$ or $C \oplus W \geq_T B$.

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.

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

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.

Source Link

R.E. Degrees B, C with all r.e. X below B computable or C join X computes B

Are there r.e. sets $B >_T 0$ and $C >_T 0$ such that for all r.e. $W \leq_T B$ either $W \leq_T 0$ or $C \oplus W \geq_T B$.

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.