# 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. – Raphael Mar 2 '15 at 11:55
• Like I said I really have no idea to prove this I guess $\leq_m$ is clear! it is mapping reduction – M a m a D Mar 2 '15 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). – Pål GD Mar 2 '15 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$. – Rick Decker Apr 1 '15 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? – M a m a D Mar 2 '15 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. – Doralisa Mar 2 '15 at 14:37