Proof by Contradiction and Contrapositive

Proving by Indirection

Sometimes a direct proof is awkward, and an indirect technique is cleaner. Two are essential.

Proof by contrapositive proves "if $p$ then $q$" by instead proving the equivalent statement "if $\neg q$ then $\neg p$" (Lesson 4: a conditional and its contrapositive are logically equivalent). This is useful when negating the conclusion gives a better starting point. To prove "if $n^2$ is even then $n$ is even," it is cleaner to prove the contrapositive "if $n$ is odd then $n^2$ is odd": write $n = 2k+1$, so $n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is odd.

Proof by contradiction (reductio ad absurdum) assumes the statement to be proved is false, then derives a logical contradiction — something that cannot be, like $0 = 1$ or "$n$ is both even and odd." Since valid reasoning cannot lead from a true assumption to a contradiction, the assumption must have been false, so the original statement is true. The classic example proves $\sqrt{2}$ is irrational: assume $\sqrt{2} = a/b$ in lowest terms; squaring gives $a^2 = 2b^2$, forcing $a$ even, then $b$ even too — contradicting "lowest terms."

The two are related but distinct: contrapositive proves $p \to q$ by directly proving $\neg q \to \neg p$ (no contradiction needed); contradiction assumes the whole statement false and hunts for any absurdity. Contradiction is more general (it can attack any statement, not just conditionals), while the contrapositive is often more direct when it applies.

Common pitfall: conflating contradiction with contrapositive. The contrapositive proves $p \to q$ by proving the equivalent conditional $\neg q \to \neg p$ directly — no absurdity is sought. Proof by contradiction assumes the statement is false and derives an impossibility. They begin with different assumptions and have different structures; mixing them up muddles the logic of the argument.