10
$\begingroup$

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.

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

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

$\endgroup$
-1
$\begingroup$

$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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.