MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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., 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|cite|improve this question
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
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|cite|improve this answer
Very nice, I definitely should have seen that! – Noah Schweber 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.