I am having a hard time proving the following $$ (a \to b) \vdash (\lnot a \to \lnot b) $$

I followed the book advice and first proved that $ (a \to b) \vdash (\lnot \lnot a \to \lnot \lnot b) $ using the Deduction Theorem but I am stuck afterwards. I have been trying to use every Axioms/Modus/Rules I know but always end up with unsatisfactory result.

A hint would be appreciated,

  • 8
    $\begingroup$ That's because it's false. It is true that one can infer $\neg b \to \neg a$ from $a \to b$ though (in classical logic anyway). $\endgroup$ – Ian Aug 26 '16 at 1:21
  • 1
    $\begingroup$ For an example of why it is false: If $n$ is a multiple of $10$ then $n$ is also a multiple of $2$. This is a true statement ($n=10k\Rightarrow n=2\cdot (5k)$). However, the statement "if $n$ is not a multiple of $10$ then it is not a multiple of $2$" is false. Take $6$ for a counterexample. $6$ happens to not be a multiple of $10$ however it is indeed a multiple of $2$. $\endgroup$ – JMoravitz Aug 26 '16 at 1:26
  • $\begingroup$ See my answer to a similar question at math.stackexchange.com/questions/1551320/… $\endgroup$ – Dan Christensen Aug 26 '16 at 4:34

If it is raining, then there are clouds out. ($a\implies b$)

If it is not raining, then there are no clouds out ($\neg a \implies \neg b$)

The first is true and the second isn't. There is something close to what you want, called contrapositive.


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.