Proof by contrapositive

Summary

A proof by contrapositive proves an implication $p \to q$ by a direct proof of $\neg q \to \neg p$. The method is correct because $p \to q$ is logically equivalent to its contrapositive.

Remarks

Example: for an integer $n$, if $n^2$ is even, then $n$ is even. The contrapositive is "if $n$ is odd, then $n^2$ is odd", which has a short direct proof. A proof by contradiction is different: it assumes $p$ and $\neg q$ together, and it gets any contradiction.

Explanations

L1 human

Sometimes the negation of the conclusion gives you more to work with. "If $n^2$ is even, then $n$ is even" is hard to start. "If $n$ is odd, then $n^2$ is odd" is easy, and it says the same thing.