A theorem says if $f$ is a computable function and we can prove $x \in A \Leftrightarrow f(x) \in B$, then we can use reduction so $A \leq_m B$.

But i'm confused if should I prove if :

  1. $(x \in A \Rightarrow f(x) \in B )\land (f(x) \in B \Rightarrow x \in A)$


  1. $(x \in A \Rightarrow f(x) \in B ) \land(x \notin A \Rightarrow f(x) \notin B)$

in which circunstances because I've seen both in demonstration. Or maybe are they equivalent ?

For example, here is a solution to the empty string problem. But with $f$ such as, $f: \text{M accepts w} \to \text{M accepts } \epsilon \\ f(\langle M, \epsilon \rangle) = \langle M \rangle$, we can proove 1. Is it valid ?


1 Answer 1


It is called contraposition :

$f(x) \in B \Rightarrow x \in A$

is equivalent to

$x \notin A \Rightarrow f(x) \notin B$.

So, the two statements that you have seen are equivalent as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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