# If $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$

How to prove if $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$ ?

it means every recursive set is mapping reducible to set $B\neq \aleph$. I really have no idea to prove this.

UPDATE

$A,B$ are sets, $A \leq_m B$ if there is a computable function $f$ such that

$A = \{ x \in N | f(x) \in B\}$

Since we have $A \leq_m B$ and $A$ is recursive, it means checking membership (characteristic function) in $A$ is recursive, so it means checking $f(x) \in B$ is recursive, right?

I guess it means $B$ must be recursive too and it means every recursive set is mapping reducible in to every other recursive set. Am I right?

• What have you tried and where did you get stuck? Hint: what kind of reduction is $\leq_m$? Unwrap the definition. Commented Mar 2, 2015 at 11:55
• Like I said I really have no idea to prove this I guess $\leq_m$ is clear! it is mapping reduction Commented Mar 2, 2015 at 12:45
• I think Raphael wants you to spell out the definition of $\leq_m$. Then you can see how a computable set might be $\leq_m$ any other set (non-empty, nor full). Commented Mar 2, 2015 at 12:49
• You're correct in saying that every recursive set is mapping reducible to every non-trivial recursive set, but as I show below, there are other $B$s for which $A\le_M B$. Commented Apr 1, 2015 at 17:31

This should be a comment on the original post by @Drupalist and on Ds D's answer, but it's too long. It's not enough to say that $A\le_M B$ requires $B$ be recursive or that one of $B, \overline B$ be r.e.

Let $A$ be recursive and $B=\{(\langle\,M\,\rangle,\langle\,N\,\rangle)\mid M,N\text{ are TMs and }L(M)=L(N)\}$. This language (sometimes called $\text{EQ}_{\text{TM}}$) is known to be neither r.e nor co-r.e. However, let

      M(x) =                    N(x) =
return accept             if x = 0
return reject
else
return accept


We have $(\langle\,M\,\rangle,\langle\,M\,\rangle)\in B$ and $(\langle\,M\,\rangle,\langle\,N\,\rangle)\in \overline{B}$. Then if $A$ is recursive, there is a decider TM, $D$, for A and if we define $f$ by

      f(x) =
run D on x
if D(x) = accept
return (<M>, <M>)
else
return (<M>, <N>)


Then $f$ is Turing-computable and $x\in A\Longleftrightarrow f(x)\in B$, which is the definition of $A\le_M B$. So we can have such a reduction in every case where it's possible to find (not necessarily by a TM) two instances $y\in B$ and $n\in\overline{B}$.

Note that I'm not claiming that this technique will work for all possible $B$ nor am I claiming that this technique is the only possible one. All I've shown is that the problem isn't as simple as it seems at first glance.

As I know the definition you gave is definition of many one reduction.

If at least one of $B$ and $B^c$ be r.e. (we can assume that B is r.e.) then we have a Turing machine $T_B$ which accept $B$ (I mean $\forall x \in B$ Turing Machine $T_B$ answer YES and halt) and another Turing machine $T_A$ that decides $A$. The computable function $f$ which we need is a function that for all input $x \in A$ which $T_A$ answers YES, $T_B$ on input $f(x)$ answer YES. it's possible to make such function so $A \leq_m B$.

If both of $B$ and $B^c$ be not r.e. then there is no Turing machine that accepts them or computes them. since we can construct a TM for all functions it's not possible to have many one reduction between $A$ and $B$.

• What is the problem with my reasoning in the update? Commented Mar 2, 2015 at 14:28
• I guess not right! I think it is true that :'every recursive set is mapping reducible in to every other recursive." but the thing that you are going to prove is something like to prove recursive is subset of r.e. Commented Mar 2, 2015 at 14:37