Proof by Contradiction

What you will get from this section. You will learn the main structure of proof by contradiction, how it grows naturally from the contrapositive, and how to use it to prove both ordinary statements and if-then statements.

The main structure of proof by contradiction

Suppose we want to prove that a statement $P$ is true.

A proof by contradiction starts by temporarily assuming that the opposite, $\neg P$, is true, and proceeds to make a chain of deductions from $\neg P$, for example:

At this point, we realise, however, that $X$ cannot actually be true, and $\neg X$ is true. Thus we have established two facts:

• (1): $\neg P \Rightarrow X$,
• (2): $\neg X$ is true.

We also know that the contrapositive of (1) is true:

• (3): $\neg X \Rightarrow \neg(\neg P)$, which is just $\neg X \Rightarrow P$.

Now combining (2) and (3), we immediately deduce that $P$ must be true. This is the high-level structure of proofs by contradiction.

A useful short way to remember it is:

Assume the opposite, deduce something impossible, then conclude the original statement is true.

Example 1: There are infinitely many prime numbers

Proof: Suppose there are only finitely many prime numbers. Now let's see what can be deduced.

$\Rightarrow$ It is then possible to make a complete and ordered list of them: $\{2,3,5,\cdots,P_n\}$, where $P_n$ is the greatest prime in the world.

$\Rightarrow$ It is possible to construct a number

that is, the product of all the primes, plus $1$.

$\Rightarrow$ $Q$ is not a multiple of $2$, or $3$, or $5$, or any prime in the list, since it is always $1$ more than a multiple of each prime by construction.

$\Rightarrow$ If $Q$ had any prime factor, that prime factor would have to be in the complete list above. But $Q$ is not divisible by any prime in the list.

$\Rightarrow$ Therefore, $Q$ is not divisible by any smaller prime.

$\Rightarrow$ $Q$ is prime.

$\Rightarrow$ $Q \leq P_n$, since $P_n$ is the greatest prime in the world.

However, this last statement cannot be right, since by construction, $Q>P_n$!

Informally, we can just say, this cannot be right, as we know $Q>P_n$. Every time we assume "there are finitely many primes", we end up in this contradiction. Therefore, this first assumption is wrong, and its negation must be true: there are infinitely many primes.

Formal proof structure: Through the proof, we have established these facts:

• (1) "There are only finitely many prime numbers" $\Rightarrow Q \leq P_n$.
• (2) $Q>P_n$ is true.

We also know that the contrapositive of (1) is true:

• (3) $Q>P_n \Rightarrow$ "There are infinitely many prime numbers".

Now combining (2) and (3), the result immediately follows. That is, there are infinitely many prime numbers, and this concludes the proof.

Example 2: $\sqrt{2}$ is irrational

Proof: Suppose $\sqrt{2}$ is rational. Now let's see what can be deduced.

$\Rightarrow$ It is possible to write $\sqrt{2}$ as a fraction in lowest terms: $\sqrt{2}=\frac{a}{b}$, where $a$ and $b$ are positive integers with no common factor greater than $1$.

$\Rightarrow$ $2=\frac{a^2}{b^2}$.

$\Rightarrow$ $a^2=2b^2$.

$\Rightarrow$ $a^2$ is even.

$\Rightarrow$ $a$ is even.

$\Rightarrow$ We can write $a=2k$ for some positive integer $k$.

$\Rightarrow$ Substituting this into $a^2=2b^2$ gives $(2k)^2=2b^2$.

$\Rightarrow$ Therefore $4k^2=2b^2$.

$\Rightarrow$ $2k^2=b^2$.

$\Rightarrow$ So $b^2$ is even.

$\Rightarrow$ $b$ is even.

$\Rightarrow$ We have now shown that $a$ and $b$ are both even, so they have a common factor of $2$.

However, this cannot be right, because $\frac{a}{b}$ was chosen to be in lowest terms.

Informally, we can just say: this cannot be right, as $a$ and $b$ cannot both be even if $\frac{a}{b}$ is in lowest terms. Every time we assume "$\sqrt{2}$ is rational", we end up in this contradiction. Therefore, this first assumption is wrong, and its negation must be true: $\sqrt{2}$ is irrational.

Formal proof structure:

Through the proof, we have established these facts:

• (1) "$\sqrt{2}$ is rational" $\Rightarrow$ "$a$ and $b$ are both even".
• (2) "$a$ and $b$ are not both even", since $\frac{a}{b}$ was chosen to be in lowest terms.

We also know that the contrapositive of (1) is true:

• (3) "$a$ and $b$ are not both even" $\Rightarrow$ "$\sqrt{2}$ is irrational".

Now combining (2) and (3), the result immediately follows. That is, $\sqrt{2}$ is irrational, and this concludes the proof.

Proving "if $P$ then $Q$" by contradiction

Sometimes we want to prove an implication:

We can rephrase this as:

So we treat $P$ as a known fact, and our goal becomes proving $Q$. The proof structure is the same as before, except that we now have the additional known fact $P$.

Example 3: if $n^2$ is odd, then $n$ is odd

We rephrase this as:

Proof: Suppose we are given that $n^2$ is odd, and assume for contradiction that $n$ is even.

$\Rightarrow$ $n=2k$ where $k$ is an integer.

$\Rightarrow$ $n^2=(2k)^2=4k^2=2(2k^2)$.

$\Rightarrow$ $n^2$ is even.

But this is wrong, since we were given that $n^2$ is odd. Every time we assume "$n$ is even", we end up in this contradiction. Therefore, this first assumption is wrong, and its negation must be true: $n$ must be odd.

Formal proof structure:

Through the proof, we have established, or know, these facts:

• (1) "$n$ is even" $\Rightarrow$ "$n^2$ is even".
• (2) "$n^2$ is odd" is true.

We also know that the contrapositive of (1) is true:

• (3) "$n^2$ is odd" $\Rightarrow$ "$n$ is odd".

Now combining (2) and (3), the result immediately follows. That is, given that $n^2$ is odd, $n$ is odd, and this concludes the proof.

Example 4: if $n^2$ is divisible by a prime $p$, then $n$ is divisible by $p$

We prove this for a positive integer $n$ and a prime number $p$.

Before we begin, the symbol $\mid$ means "divides". For example:

means "$p$ divides $n$", or equivalently, "$n$ is divisible by $p$".

We prove this for a positive integer $n$ and a prime number $p$.

We rephrase the statement as:

Proof: Suppose we are given that $p \mid n^2$, and assume for contradiction that $p \nmid n$.

$\Rightarrow$ Since $p$ is prime and $p \nmid n$, the prime $p$ does not appear in the prime factorisation of $n$.

$\Rightarrow$ Therefore, $p$ does not appear in the prime factorisation of $n^2$.

$\Rightarrow$ $p \nmid n^2$.

But this is wrong, since we were given that $p \mid n^2$. Every time we assume "$p \nmid n$", we end up in this contradiction. Therefore, this first assumption is wrong, and its negation must be true: $p \mid n$.

Formal proof structure:

Through the proof, we have established, or know, these facts:

• (1) "$p \nmid n$" $\Rightarrow$ "$p \nmid n^2$".
• (2) "$p \mid n^2$" is true.

We also know that the contrapositive of (1) is true:

• (3) "$p \mid n^2$" $\Rightarrow$ "$p \mid n$".

Now combining (2) and (3), the result immediately follows. That is, given that $p \mid n^2$, $p \mid n$, and this concludes the proof.

Summary

• To prove $P$ by contradiction, assume $\neg P$.
• Then deduce something impossible.
• Since $\neg P$ leads to something impossible, $\neg P$ cannot be true.
• Therefore $P$ must be true.
• For an if-then statement $P \Rightarrow Q$, treat $P$ as a known condition and prove $Q$ by contradiction.
• The logical structure is closely connected to the contrapositive: if $\neg P \Rightarrow X$ and $\neg X$ is true, then $P$ must be true.

Worksheets

Practise proving statements by contradiction: assuming the opposite $\neg P$, deducing an impossible consequence, and concluding that $P$ must be true — including classic examples and how the method relates to the contrapositive. Each worksheet below comes as a PDF with fully worked solutions.

• Worksheet 1 — Questions · Solutions