Logical equivalences for $P \implies Q$ and $\neg Q \implies \neg P$

Question

This is probably quite a basic question, but it's something I'm having trouble wrapping my head around.

I came across a proof which employed the following strategy

The goal was to prove

$$P \implies Q$$

And the strategy used was to prove the following instead:

$$\neg Q \implies \neg P$$

If possible, could someone provide some intuition as to why these two statements would be equivalent?

Answer 1

$P \implies Q$ means whenever you have $P$ you will have $Q$.

That means if you have $P$ then $\lnot Q$ is impossible.

That means if you do have $\lnot Q$, it isn't possible that you had $P$ (because then you would have had $Q$).

That means if you have $\lnot Q$ then you will have $\lnot P$.

That means $\lnot Q \implies \lnot P$.

... So if "$P \implies Q$" is true it is also true that "$\lnot Q \implies \lnot P$".

====

Likewise $\lnot Q \implies \lnot P$ means whenever $Q$ is false then $P$ is false.

So if you have $P$ is true it isn't possible that you had $Q$ is false (because if $Q$ is false $P$ wouldn't be true.)

So if somehow you had $P$ is true and it isn't possible that $Q$ is false, it must be that $Q$ is true.

So if you did have $P$ is true it must follow that $Q$ is true.

So $P \implies Q$.

... So if "$\lnot Q \implies \lnot P$" is true it will follow that "$P \implies Q$" is true.

====

So the two statements $P\implies Q$ and $\lnot Q \implies \lnot P$ can only be true if the other one is true, and if one is false the other can't be true and if one is true the other must also be true, these two statements are always true or false under the exact same circumstances.

In other words... they are equivalent statements.

Answer 2

In classical logic this boils down to the definition of $\implies$. You can then check this equivalence by testing all possible combinations of truth values for $P$ and $Q$. This principle is called contraposition.

In intuitionistic logic, you only get that $P\implies Q$ implies $\lnot Q\implies \lnot P$, but not the converse.

Contraposition is often a convenient way of starting a proof, in particular if you don't know where you want to go with your proof. But many such proofs can be in fact reformulated to be direct proofs.

Answer 3

If $P$ implies $Q$, then $\lnot Q$ cannot imply $P$; because that would in turn imply $Q$ (a contradiction).   So therefore must $\lnot Q$ imply $\lnot P$.

That is: $P\to Q$ entails that $\lnot Q\to\lnot P$.

---

Likewise if $\lnot Q$ implies $\lnot P$, then $P$ cannot imply $\lnot Q$; because that would in turn imply $\lnot P$ (a contradiction).   So therefore must $P$ imply $\lnot\lnot Q$.

In classical logic, that double negation can be eliminated, so we can say $\lnot Q\to\lnot P$ entails $P\to Q$.