Proof by Contradiction

Assume the opposite, derive absurdity, conclude the original — the technique of √2, primes, and Gödel.

The idea

Proof by contradiction (reductio ad absurdum) establishes a statement $P$ by showing that its negation is untenable. Assume that $P$ is false, reason from that assumption, and derive a statement that cannot hold — a contradiction, typically a statement $A$ and its negation $\neg A$ both true. Correct reasoning from true premises yields only true conclusions, so the assumption $\neg P$ must itself be false, and therefore $P$ is true.

The method is useful because the negation is often easier to reason from than the claim itself. Many claims assert that no object of a certain kind exists, and such a claim offers nothing to compute with. The assumption $\neg P$ supplies the very object the claim denies, together with every property such an object would have to have, and the proof derives an impossibility from those properties.

Two errors are common. Negating the claim incorrectly makes every later line reason from the wrong assumption. And the proof is complete only when the derived statement is genuinely impossible, not merely surprising.

Ways to work on it

• Walkthrough. The structure of contradiction proofs, with two famous examples.
• Practice. Negate a statement correctly to set up a proof by contradiction.
• Hardest. Negate nested-quantifier statements — the kind that show up in real analysis.

Not sure where to start? Take the ten-question placement test.