Proof by contradiction, the structure of the method, and the classic results proved this way (the irrationality of root 2, the infinitude of primes).

What this dot point is asking

WJEC wants you to prove statements by contradiction: assume the statement is false, reason validly until you reach an impossibility, and conclude that the original statement must be true. The specification expects you to be able to reproduce the classic proofs, including the irrationality of $\sqrt{2}$ and the infinitude of the primes, and to apply the method to unfamiliar statements. Clear logical structure is everything here.

The answer

The structure of the method

Proof by contradiction (also called reductio ad absurdum) reverses the usual direction. Instead of building up to the conclusion, you suppose the conclusion is false and show that this supposition cannot hold.

A complete answer always has three visible parts: the assumption (stated as "Assume, for contradiction, that ..."), the chain of valid steps, and the contradiction named explicitly, followed by the conclusion.

The irrationality of root 2

This is the most-examined example. The key move is assuming the fraction is in lowest terms, because the contradiction is that the numerator and denominator turn out to share a factor.

The infinitude of the primes

Euclid's argument: assume there are only finitely many primes $p_1, p_2, \ldots, p_n$. Form $N = p_1 p_2 \cdots p_n + 1$. Then $N$ leaves remainder $1$ when divided by each prime, so no prime in the list divides $N$. Hence either $N$ is itself a new prime, or it has a prime factor not in the list. Either way there is a prime beyond the list, contradicting the assumption that the list was complete.

Examples in context

Example 1. No rational square root of 3. The same template proves $\sqrt{3}$ is irrational: assume $\sqrt{3} = \dfrac{a}{b}$ in lowest terms, square to get $a^2 = 3b^2$, deduce $a$ is a multiple of $3$, then $b$ is too, contradicting lowest terms. The structure transfers directly to any non-square integer.

Example 2. A logical impossibility. To prove "if $n^2$ is odd then $n$ is odd", assume $n^2$ is odd but $n$ is even. Then $n = 2k$ gives $n^2 = 4k^2$, which is even, contradicting $n^2$ being odd. The contradiction settles it without a direct argument.

Try this

Q1. State the first line of a proof by contradiction that $\sqrt{5}$ is irrational. [1 mark]

• Cue. "Assume, for contradiction, that $\sqrt{5} = \dfrac{a}{b}$ in lowest terms with $b \neq 0$."

Q2. In Euclid's prime proof, why does $N = p_1 \cdots p_n + 1$ have no prime factor in the list? [2 marks]

• Cue. Dividing $N$ by any $p_i$ leaves remainder $1$, so no $p_i$ divides $N$.

Q3. Prove by contradiction that there is no smallest positive rational number. [3 marks]

• Cue. Assume $q$ is the smallest; then $\tfrac{q}{2}$ is a smaller positive rational, a contradiction.