Proof by Contradiction

In one sentence

Proof by contradiction: to prove $A \Rightarrow B$ , assume first that $B$ is false. Treat “not $B$ ” as a new condition, reason with it together with $A$ , and keep going until you reach a contradiction: with the given conditions, with a theorem, or with itself. Since “not $B$ ” cannot stand, $B$ is true.

Three moves: assume the opposite (state the negation of the conclusion precisely) → derive a contradiction (the key step) → conclude.

Example: there are infinitely many primes (Euclid)

Step 1 / 4

Assume the opposite
Suppose there are only finitely many primes, and list all of them: $p_{1}, p_{2}, \dots, p_{k}$ . In the picture, start with $2, 3, 5$ .

$all primes = {p_{1}, \dots, p_{k}}$
Build a number
Derive a contradiction
Conclusion

Predict first

Suppose all the primes are $2, 3, 5, 7, 11, 13$ . Then $N = 2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031$ . Is $30031$ prime?

It is primeIt is not prime

Choose an answer first; then you can see the result.

Stop 1 · Properties of Sets (Vol. 1)

“The set $A$ cannot have just one element.” The conclusion is negative, and it is hard to know where to start directly. Assume it has just one element, and the condition at once becomes an equation.

Example: a set A of real numbers satisfies 1 ∉ A, and if a ∈ A then 1/(1 − a) ∈ A. Prove that A cannot have exactly one element

Step 1 / 4

Assume the opposite
Suppose $A = {a}$ has just one element, where $a \neq = 1$ .

$A = {a}$
Use the condition
Derive a contradiction
Conclusion

Stop 2 · The well-ordering principle (Vol. 5)

Team up proof by contradiction with “smallest”, and you get infinite descent: assume there is a solution, take the “smallest” one, then build an even smaller one. Contradiction.

One problem, several solutions

Prove that $2$ is irrational.

Lowest terms + parity

Assume $2 = \frac{p}{q}$ , where $p, q$ are coprime positive integers. Then $p^{2} = 2 q^{2}$ , so $p^{2}$ is even, and therefore $p$ is even.

Write $p = 2 r$ . Then $q^{2} = 2 r^{2}$ , so $q$ is even too. Both $p$ and $q$ are even, contradicting the fact that they are coprime.

CostThe most common proof; you must say “in lowest terms” first.

Infinite descent (well-ordering principle)

Assume $2 = \frac{p}{q}$ . Among all such representations, the positive integer $q$ has a smallest value; take a representation with the smallest $q$ .

As before, $p^{2} = 2 q^{2}$ gives $p = 2 r$ and $q^{2} = 2 r^{2}$ . So $2 = \frac{q}{r}$ , and $r = \frac{p}{2} < q$ (because $p < 2 q$ ).

We have found a representation with a smaller denominator, contradicting the choice of the smallest $q$ .

CostNo “lowest terms”; use “smallest denominator” instead. The same skeleton proves that many Diophantine equations have no solutions.

Stop 3 · Functional equations (Vol. 2)

“No such function exists”: another negative conclusion. Assume it exists, and use special values to back it into a corner.

Example: prove there is no injection f: ℝ → ℝ such that f(x²) − (f(x))² ≥ 1/4 for every real x

Step 1 / 4

Assume the opposite
Suppose such an injection $f$ exists. The condition holds for every $x$ ; pick the values with $x^{2} = x$ .

$x^{2} = x ⟺ x = 0 or 1$
Put x = 0
Put x = 1
Derive a contradiction

Practice

Exercise 1Basic

Suppose all the primes are $2, 3, 5, 7, 11, 13$ . Build $N$ as Euclid did. What is the smallest prime factor of $N$ ?

Exercise 2Advanced

How many integer solutions does the equation $x^{2} - y^{2} = 2022$ have?

Exercise 3Advanced

Prove that $lo g_{2} 3$ is irrational.

Exercise 4Challenge

Let $a, b, c$ all be odd. Prove that the equation $a x^{2} + b x + c = 0$ has no rational root.

In one sentence

Example: there are infinitely many primes (Euclid)

Stop 1 · Properties of Sets (Vol. 1)

Example: a set A of real numbers satisfies 1 ∉ A, and if a ∈ A then 1/(1 − a) ∈ A. Prove that A cannot have exactly one element

Stop 2 · The well-ordering principle (Vol. 5)

Lowest terms + parity

Infinite descent (well-ordering principle)

Stop 3 · Functional equations (Vol. 2)

Example: prove there is no injection f: ℝ → ℝ such that f(x²) − (f(x))² ≥ 1/4 for every real x

Practice

Mistake Museum · Exhibits from this stop

The negation is wrong

A “contradiction” that never uses the assumption

Stops on this line