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

Question

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?

Answer 1

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.

Answer 2

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$.