Some claims resist a direct attack, and two indirect routes are available. A proof by contradiction assumes the claim is false and derives an impossibility, so the assumption cannot stand. A proof by contrapositive assumes the conclusion fails and derives that the hypothesis fails too, which says the same thing as the original.

Contradiction is an alibi in reverse: suppose the suspect was at the scene, and note that he was filmed elsewhere at that hour. The supposition collapses. The contrapositive is quieter: rather than showing rain wets the ground, show that dry ground means it did not rain.

Both replace the claim with something easier to argue about. Their openings are different and confusing them is the usual source of trouble: one negates the whole statement, the other only its conclusion.

• By contradiction: assume the whole statement is false, then reach something impossible.
• By contrapositive: assume $\neg Q$, then derive $\neg P$, which proves $P \implies Q$.
• The contrapositive is a direct proof of an equivalent statement, so nothing impossible need appear.
• The negation of $P \implies Q$ is , which is where a proof by contradiction of an implication starts.

Suppose such a largest number existed. Adding one to it produces a natural number that is larger, which the supposition forbids. The supposition therefore cannot hold.

Assume the opposite of what is claimed, and see where it leads.

Adding one to a natural number never leaves the natural numbers.

Adding one strictly increases a number.

We have produced a natural number the supposed maximum does not reach.

The supposition led to an impossibility, so it must be rejected.

If the assumption forces an impossibility, the assumption itself is impossible and $S$ stands.

No implication appears on the right, which is what makes the assumption something you can work with.

This is an ordinary direct proof, only of the contrapositive, which carries the same truth value.

If $n^2$ is odd then $n$ is odd.

Assuming $n$ even gives an equation immediately, whereas assuming $n^2$ odd gives much less to grip.

Both start by assuming something false. They differ in what they then have to reach.

• Contradiction: assume the denial of the whole claim and reach an absurdity.
• Contrapositive: assume $\neg Q$ and derive $\neg P$, which is a direct proof of an equivalent statement.
• The denial of $P\implies Q$ is $P\land\neg Q$, which is where a proof by contradiction of an implication starts.

Great work! You now know how to:

• Open a proof by contradiction with the correct denial
• Open a proof by contrapositive and say what is to be derived
• Choose between the two methods by looking at what each hands you