I'm studying for my final in theory of computation, and I'm struggling with the proper way of answering whether this statement is true of false.

By the definition of $\leq_m$ we can construct the following statement,

$w \in A \iff f(w) \in B \rightarrow w \notin A \iff f(w) \notin B$

This is where I'm stuck, I want to say that since we have such computable function $f$ then it'll only give us the mapping from A to B if there is one, otherwise it wont.

I don't know how to phrase this correctly, or if I'm even on the right track.

  • $\begingroup$ This relies purely on logic, namely that $A\implies B$ is logically equivalent to $\neg B\implies \neg A$. $\endgroup$ Apr 26, 2012 at 20:45
  • 1
    $\begingroup$ You should provide context and define your notation ($\Leftrightarrow$, $\rightarrow$, $\le_m$). But if you are using common notations ($\Leftrightarrow$ is logical equivalence, $\rightarrow$ is implication, and the setting is classical logic) then Dave's comment and Kaveh's answer are correct. $\endgroup$ Apr 26, 2012 at 22:30

2 Answers 2


As Dave said, it follows from a simple logical equivalence: $p \leftrightarrow q$ is the same as $\lnot p \leftrightarrow \lnot q$. Now put $p= w\in A$ and $q = f(w) \in B$.

$A \leq_m B$ means there is a total computable $f$ s.t. for all $w$,

$w \in A \leftrightarrow f(w) \in B$.

By the argument above, this is the same as

$w \notin A \leftrightarrow f(w) \notin B$.

Or equivalently

$w \in \bar{A} \leftrightarrow f(w) \in \bar{B}$.

And therefore, the same $f$ shows that $\bar{A} \leq_m \bar{B}$.


$A \leq_m B$ does not implie $w \in A \leftrightarrow f(w) \in B$ only the other way is true if $w \in A \leftrightarrow f(w) \in B$ then $A \leq_m B$ but not reciprocaly

  • $\begingroup$ Why do you say that? AFAIK, $A\le_M B$ is defined to be "there exists a Turing-computable total function $f$ such that $w\in A\Longleftrightarrow f(w)\in B$". $\endgroup$ Apr 1, 2015 at 17:40

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.