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

Problem Detail: 

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.

Asked By : trigoman

Answered By : Kaveh

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1517