Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
The answer is no. Let $Y$ be the halting problem and $X$ be a 1-generic set below $Y$. –  Liang Yu Apr 2 '14 at 2:17

1 Answer 1

up vote 10 down vote accepted

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.

share|improve this answer
Very nice, I definitely should have seen that! –  Noah S Apr 2 '14 at 3:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.