To prove $p\rightarrow q$, it suffices to prove $\neg q\rightarrow \neg p$. The reason is if I proved $\neg q\rightarrow \neg p$, that means there is no case where $\neg q$ is true and $\neg p$ is false($q$ is false and $p$ is true.) so when I assume p is true q must be true. Is this how contrapositive proof works?
Asked
Active
Viewed 83 times
3
-
2You can write out the truth tables for both of these if you really want to convince yourself – Ty Jensen Feb 10 '20 at 21:59
-
Here's a useful tool. – Shaun Feb 10 '20 at 22:46
2 Answers
3
Indeed.
Every evaluation that holds $\neg q\to\neg p$ as true and $q$ as false must value $p$ as false (via modus ponens).
So any evaluation that holds $\neg q\to\neg p$ as true and $p$ as true therefore must value $q$ as true (because doing otherwise would produce a contradiction).
Thus we deduce that $\neg q\to\neg p$ logically entails $p\to q$.
Graham Kemp
- 129,094
2
That's one way of putting it. We can make what you're doing here more formal with the concept of truth tables. We start with $2^2=4$ possible choices of the truth-values of $p,\,q$, each either true or false. You reason that $\neg q\to\neg p$ is telling us we don't keep any of these $4$ cases for which $\neg q$ is true and $\neg p$ is false. In other words, we eliminate exactly $1$ case, the one for which $\neg p\land q$. We then note each of the surviving cases makes $p\to q$ true. In fact, since the remaining cases and only the remaining cases do this, $p\to q$ is equivalent to $\neg q\to\neg p$, i.e. either statement can prove the other.
J.G.
- 115,835