Proof by Contradiction

Why This Matters

Proof by contradiction (Latin: reductio ad absurdum) is the most flexible non-constructive technique a proof writer has. The structure:

To prove $P$ , assume $\neg P$ and derive a contradiction. Conclude $P$ .

The technique works because, classically, $\neg \neg P \Leftrightarrow P$ . You exploit the negation by extracting concrete consequences of $\neg P$ , then push those consequences until two of them collide.

Recognize proof by contradiction when:

The conclusion is a non-existence statement ("there is no rational $r$ with $r^2 = 2$ ", "there are no integer solutions to ...").
The conclusion is an infinitude statement ("there are infinitely many primes").
A direct proof requires constructing a witness you cannot see, but a contradiction witness is easy to manipulate.
The negation has more structure than the original statement. Negating "for all $x$ , $P(x)$ " yields "there exists $x$ with $\neg P(x)$ ", an existential witness you can then chase.

Proof by contradiction is closely related to proof by contrapositive ( $P \Rightarrow Q$ is equivalent to $\neg Q \Rightarrow \neg P$ ) and infinite descent (a particular shape of contradiction that produces an infinite decreasing sequence in $\mathbb{N}$ ). They are three faces of the same non-constructive impulse.

The Irrationality of $\sqrt{2}$

Theorem

Irrationality of the Square Root of Two (Pythagoreans, c. 500 BCE)

Statement

There is no rational number $\frac{p}{q}$ such that $\left(\frac{p}{q}\right)^2 = 2$ .

Intuition

The proof is the canonical introduction to contradiction: assume $\sqrt{2}$ is rational, write it in lowest terms, extract a parity contradiction. The argument is clean because the negation (" $\sqrt{2}$ is rational") gives you a concrete fraction to manipulate, while a direct proof would have to work with the whole real line.

Proof Sketch

Suppose, for contradiction, that $\sqrt{2} = \frac{p}{q}$ with $p, q \in \mathbb{Z}$ , $q \ne 0$ , and $\gcd(p, q) = 1$ (this last assumption is the load-bearing setup move; without it the argument loops).

Then $p^2 = 2 q^2$ , so $p^2$ is even, so $p$ is even. Write $p = 2m$ . Then $4 m^2 = 2 q^2$ , so $q^2 = 2 m^2$ , so $q^2$ is even, so $q$ is even.

But $p$ even and $q$ even contradicts $\gcd(p, q) = 1$ . Hence no such $p, q$ exist, and $\sqrt{2}$ is irrational.

Why It Matters

The Pythagoreans famously hid this result because it broke their philosophical commitment to ratios of whole numbers. The proof became the template for all subsequent irrationality proofs: assume rationality, write in lowest terms, extract a divisibility contradiction. The same shape proves $\sqrt{n}$ irrational whenever $n$ is not a perfect square, and similar arguments handle $e$ and $\pi$ (with much more work).

Failure Mode

The proof relies on " $p^2$ even $\Rightarrow$ $p$ even", which in turn relies on unique prime factorization. Over rings that lack unique factorization (some number-theoretic settings), the parity step does not transfer cleanly and the argument must be adapted.

Also: the lowest-terms hypothesis is essential. Without it the descent loops forever, extracting factors of 2 but never close the contradiction.

report a correction →

Euclid's Infinitude of Primes

Example

Euclid, Elements Book IX Proposition 20

Problem. Show that there are infinitely many prime numbers.

Solution. Suppose, for contradiction, that the set of primes is finite, say $\{p_1, p_2, \ldots, p_n\}$ .

Consider the integer $N = p_1 p_2 \cdots p_n + 1$ . Either $N$ is prime, or $N$ has a prime factor $p$ . In the first case $N$ is a prime not in the original list (since $N > p_i$ for every $i$ ), contradicting the assumption that the list was exhaustive. In the second case, $p$ divides $N$ but also divides $p_1 \cdots p_n$ , so $p$ divides $N - p_1 \cdots p_n = 1$ , which is impossible.

Either way we reach a contradiction, so the set of primes is infinite.

A frequent confusion: $N$ in Euclid's argument is not always prime (the smallest counterexample is $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ ). The proof does not claim $N$ is prime; it claims $N$ has a prime factor not on the list. This is a standard misreading.

The Logical Structure

A proof by contradiction has three parts:

Setup. State the negation cleanly. "Suppose, for contradiction, that $\neg P$ ." Make the negation concrete: if $P$ is "for all $x$ , $\varphi(x)$ ", then $\neg P$ is "there exists $x_0$ with $\neg \varphi(x_0)$ "; fix that $x_0$ explicitly.
Derivation. Use the assumption to derive consequences, typically two consequences that can be combined into a contradiction. The cleanest contradictions look like $0 = 1$ , $\gcd(p, q) > 1$ contradicting $\gcd(p, q) = 1$ , or " $n < n$ " derived in some auxiliary structure.
Closure. State the contradiction explicitly and conclude $P$ . Do not leave the contradiction implicit.

The setup move, naming the negation precisely, is where beginners stumble. Negating quantified statements is a mechanical operation but the mechanics are easy to forget under problem-solving pressure.

Worked Example: $\log_2 3$ is Irrational

Example

$\log_2 3$ is irrational

Problem. Show that $\log_2 3$ is not a rational number.

Solution. Suppose, for contradiction, that $\log_2 3 = \frac{p}{q}$ with $p, q$ positive integers (positive because $\log_2 3 > 0$ ).

Then $2^{p/q} = 3$ , so $2^p = 3^q$ . The left side is a power of 2, hence has only the prime 2 in its factorization. The right side is a power of 3, hence has only the prime 3 in its factorization.

By unique factorization in $\mathbb{Z}$ , the only way $2^p = 3^q$ is $p = q = 0$ , contradicting $p, q \ge 1$ .

Hence $\log_2 3$ is irrational.

The shape generalizes immediately: $\log_a b$ is irrational whenever $a, b$ are positive integers with disjoint prime factorizations and $b \ne 1$ .

Common Mistakes

Watch Out

Begging the question

The most common error is assuming, in the contradiction argument, the very statement you are trying to prove. If the "contradiction" relies on $P$ itself, the proof is circular. After deriving the contradiction, re-read the proof and check that nothing in the chain assumed $P$ .

Watch Out

Negating the wrong scope

Negating "for all $x$ in $S$ , $\varphi(x)$ " gives "there exists $x_0$ in $S$ with $\neg \varphi(x_0)$ ", not "for all $x$ in $S$ , $\neg \varphi(x)$ ". The quantifier flips. Beginners sometimes negate just the inner predicate and keep the quantifier. That produces a much stronger statement than the real negation, often unprovable, and the proof stalls.

Watch Out

Stopping at a non-contradiction

A "weird" or "surprising" consequence is not yet a contradiction. The conclusion $\neg P$ must be incompatible with something definitely known to be true (an axiom, a theorem, a hypothesis of the problem). Until you state which known fact is contradicted, the proof is incomplete.

Watch Out

Using contradiction when a direct proof is shorter

Many proofs are dressed up as contradiction proofs out of habit when the direct version is cleaner. If your contradiction argument never uses the negation in any essential way (if you could delete the "suppose not" line and the rest still works), the direct proof is better.

Watch Out

Constructive limits

Proof by contradiction relies on the law of excluded middle: $P \vee \neg P$ . In intuitionistic logic this is rejected, and contradiction proofs of positive existence are not valid: a contradiction proof of "there exists $x$ with $\varphi(x)$ " does not exhibit the witness. For olympiad and standard mathematics this is irrelevant; for foundations, type theory, and constructive computer science, it matters.

Exercises

ExerciseCore

Problem

Show that $\sqrt{3}$ is irrational, following the template of the $\sqrt{2}$ proof. Where does the parity argument get replaced?

ExerciseCore

Problem

Show that the equation $x^2 - 2 y^2 = 0$ has no positive integer solutions $(x, y)$ .

ExerciseAdvanced

Problem

Prove that there is no continuous bijection $f: [0, 1] \to [0, 1]^2$ (no continuous bijection from the unit interval to the unit square).

Cross-Network Links

ProofsPath: proof-by-contrapositive is the close cousin: $P \Rightarrow Q$ becomes $\neg Q \Rightarrow \neg P$ , often producing a cleaner argument with the same logical content; proof-by-infinite-descent is contradiction in number-theoretic disguise (the contradiction is an infinite decreasing sequence of natural numbers); well-ordering-principle is the axiom underwriting infinite-descent contradictions.
TheoremPath: law-of-large-numbers uses contradiction-style arguments in some classical proofs (the Etemadi proof, for instance, uses subsequence contradictions).
ComputationPath: contradiction proofs that fail in constructive settings are the boundary case for type theory and proof assistants with intuitionistic foundations.

References

See structured references block. Primary entry points: Velleman How to Prove It Ch 3 for the technique with worked examples; Hardy Pure Mathematics Ch 1 for classical irrationality proofs; Aigner-Ziegler Proofs from THE BOOK for elegant contradiction arguments throughout; Dummett Elements of Intuitionism for the constructive critique.

Proof by Contradiction

Proof by Contradiction

Why This Matters

The Irrationality of 2\sqrt{2}2​

Euclid's Infinitude of Primes

The Logical Structure

Worked Example: log⁡23\log_2 3log2​3 is Irrational

Common Mistakes

Exercises

Cross-Network Links

References

The Irrationality of $\sqrt{2}$

Worked Example: $\log_2 3$ is Irrational