# Interaction between Turing and many-one reducibility

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.

-
The answer is no. Let $Y$ be the halting problem and $X$ be a 1-generic set below $Y$. – 喻 良 Apr 2 '14 at 2:17

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.