HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

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

Submitted by: @import:stackexchange-cs··
0
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.

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

Context

StackExchange Computer Science Q#1517, answer score: 18

Revisions (0)

No revisions yet.