# Turing reducibility implies mapping reducibility

The question is whether the following statement is true or false:

$A \leq_T B \implies A \leq_m B$

I know that if $A \leq_T B$ then there is an oracle which can decide A relative to B. I know that this is not enough to say that there is a computable function from A to B that can satisfy the reduction.

I don't know how to word this in the proper way or if what I'm saying is enough to say that the statement is false. How would I go about showing this?

EDIT: This is not a homework problem per se, I'm reviewing for a test. Where $\leq_T$ is Turing reducibility, and $\leq_m$ is mapping reducibility.

## 3 Answers

The statement is false.

Say B is the Halting problem and $A = \overline B$. Then, given oracle to the halting problem we can easily decide its complement.

However it is not true that $A \le_m B$ since $B\in RE$ and $A\in coRE$ but both are undecidable (i.e., if $A \le_m B$ was true, then $B=HP$ is both in $RE$ and $coRE$, that is, $B\in R$ which is a contradiction).

It is false: take $Diag = \{\langle M \rangle \mid M \notin L(M) \}$ and its complement.

Generally $\leq_T$ can be used to reduce a problem to its complement while $\leq_m$ cannot.

If you want to know see more kinds of reductions and examples that they are different I suggest having a look at "Classical Recursion Theory" by Odifreddi.

There is a general fact that every noncomputable Turing degree contains infinitely many distinct $m$-degrees.

(This result follows at least from results of Jockusch, "Relationships between reducibilities", Trans. Amer. Math. Soc. 142 (1969), 229-237. It might have been known before that.)