This is a question about two reducibility notions in computability theory. I suspect the answer is a fairly simple construction, and I'm just not seeing it.


For sets $X, Y\subseteq\omega$, we say $X$ is *Turing reducible to* $Y$ if there is a Turing machine $\Phi$ which, when given $Y$ as an oracle, yields (the characteristic function of) $X$, and we write $X\le\_T Y$. We say $X$ is *many-one reducible to* $Y$ if there is some computable function $f$ such that $f(x)\in Y\iff x\in X$, and we write $X\le\_mY$. Clearly many-one reducibility strictly implies Turing reducibility. A bit less clearly, the many-one degrees within a single Turing degree form a surprisingly large and interesting structure (see e.g. <http://www.jstor.org/stable/2695042?seq=1>, which among other things taught me that "objective" and "subjective" are technical terms in computability theory).


My question is the following:



> 
> Suppose $X\le\_T Y$. Is there a set $A\equiv\_T X$ such that $A\le\_mY$?
> 
> 
> 


Note that it is important that $Y$ is kept fixed, here: we of course always have $X\le\_m Y\oplus X$, so allowing $Y$ to vary would make the question trivial. This observation amounts to saying that the relation $\le\_m\subseteq deg(X)\times deg(Y)$ is total; and the question I am asking is whether it is surjective as well.



Interaction between Turing and many-one reducibility
No. A set is $m$-reducible to the Halting Problem iff it is computably enumerable, so let $Y$ be the Halting Problem and let $X$ be any $\Delta^0\_2$ set not of c.e. Turing degree.


