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= win 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
