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.


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

  • $\begingroup$ What have you tried and where did you get stuck? Hint: what kind of reduction is $\leq_m$? Unwrap the definition. $\endgroup$
    – Raphael
    Commented Mar 2, 2015 at 11:55
  • $\begingroup$ Like I said I really have no idea to prove this I guess $\leq_m$ is clear! it is mapping reduction $\endgroup$
    – M a m a D
    Commented Mar 2, 2015 at 12:45
  • 1
    $\begingroup$ 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). $\endgroup$
    – Pål GD
    Commented Mar 2, 2015 at 12:49
  • $\begingroup$ 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$. $\endgroup$ Commented Apr 1, 2015 at 17:31

2 Answers 2


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

  • $\begingroup$ What is the problem with my reasoning in the update? $\endgroup$
    – M a m a D
    Commented Mar 2, 2015 at 14:28
  • $\begingroup$ 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. $\endgroup$
    – Doralisa
    Commented Mar 2, 2015 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.