# If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B

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.

• This relies purely on logic, namely that $A\implies B$ is logically equivalent to $\neg B\implies \neg A$. – Dave Clarke Apr 26 '12 at 20:45
• 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. – Gilles Apr 26 '12 at 22:30

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

• 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$". – Rick Decker Apr 1 '15 at 17:40