patternModerate
If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B
Viewed 0 times
thereduciblethencomplementmapping
Problem
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.
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.
Solution
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$ 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}$.
Context
StackExchange Computer Science Q#1517, answer score: 18
Revisions (0)
No revisions yet.