Proof by contradiction: method and examples

Proof by contradiction establishes a statement by assuming that it is false and showing that this assumption leads inevitably to an impossibility. Since the assumption cannot be true, the original statement must be true.

The logical shape is:

$$\text{assume }\neg P \quad\Longrightarrow\quad \text{contradiction} \quad\Longrightarrow\quad P.$$

Here $P$ is the statement to be proved and $\neg P$ means “not $P$”. The contradiction might be a false numerical claim such as $0=1$, incompatible conclusions such as “the integer $n$ is both even and odd”, or a direct conflict with a given assumption.

Prerequisites

You should be able to:

• use the definitions of even, odd, rational, irrational and prime numbers
• manipulate fractions and surds
• use algebra to form a chain of deductions
• distinguish a proof from evidence provided by examples

Review proof and reasoning if mathematical implications or universal statements are unfamiliar.

The method

To prove a statement $P$ by contradiction:

1. Assume the opposite. State clearly that $P$ is false.
2. Translate the assumption into mathematics. Use exact definitions.
3. Deduce consequences. Every step must follow from the assumption, the givens or an established fact.
4. Identify the contradiction. Say exactly which two claims are incompatible.
5. Conclude. Reject the assumption and state that $P$ is therefore true.

The hardest step is often the first. The opposite must be the logical negation, not merely a different statement.

Statement	Correct negation
$x=3$	$x\ne3$
$x>3$	$x\leq3$
$n$ is even	$n$ is odd, when $n$ is an integer
Every integer has property $Q$	At least one integer does not have property $Q$
There exists an integer with property $Q$	No integer has property $Q$

For example, the negation of $x>0$ is $x\leq0$, not $x<0$. Forgetting the boundary value $x=0$ leaves a logical gap.

Example 1: no greatest integer

Prove that there is no greatest integer.

Assume, for contradiction, that there is a greatest integer. Call it $N$.

Since $N$ is an integer, $N+1$ is also an integer. But

$$N+1>N.$$

This contradicts the assumption that $N$ is the greatest integer. Therefore there is no greatest integer.

Notice that the contradiction is not merely that $N+1$ is large. It is that an integer greater than the supposed greatest integer has been constructed.

Example 2: irrationality of $\sqrt{2}$

Prove that $\sqrt{2}$ is irrational.

Assume, for contradiction, that $\sqrt{2}$ is rational. Then it can be written in lowest terms as

$$\sqrt{2}=\frac{a}{b},$$

where $a,b\in\mathbb Z$, $b\ne0$, and $a$ and $b$ have no common factor greater than $1$.

Square both sides:

$$2=\frac{a^2}{b^2} \quad\Longrightarrow\quad a^2=2b^2.$$

Therefore $a^2$ is even. If $a$ were odd, $a=2k+1$ for some integer $k$, giving

$$a^2=(2k+1)^2=2(2k^2+2k)+1,$$

which is odd. Hence $a$ must be even. Write $a=2m$.

Substitute this into $a^2=2b^2$:

$$(2m)^2=2b^2 \quad\Longrightarrow\quad 4m^2=2b^2 \quad\Longrightarrow\quad b^2=2m^2.$$

The same reasoning shows that $b$ is even. Thus $a$ and $b$ are both divisible by $2$, contradicting the statement that $a/b$ was in lowest terms. Therefore $\sqrt{2}$ is irrational.

Why “lowest terms” matters

Finding that $a$ and $b$ are both even is not impossible by itself. For example, $2/4$ is a valid fraction. The contradiction occurs because $a/b$ was specifically chosen in lowest terms. Any rational number can be expressed in lowest terms, so this choice loses no generality.

Example 3: rational plus irrational

Let $r$ be rational and let $x$ be irrational. Prove that $r+x$ is irrational.

Assume, for contradiction, that $r+x$ is rational. Let

$$r+x=q,$$

where $q$ is rational. Rearranging gives

$$x=q-r.$$

The difference of two rational numbers is rational: if $q=a/b$ and $r=c/d$, then

$$q-r=\frac{ad-bc}{bd},$$

which is a ratio of integers with non-zero denominator. Hence $x$ is rational. This contradicts the given fact that $x$ is irrational. Therefore $r+x$ is irrational.

This proof illustrates a useful strategy: when the statement involves an irrational number, assume the result is rational and rearrange to force the original irrational number to be rational.

Example 4: divisibility

Prove that if $n^2$ is divisible by $3$, then $n$ is divisible by $3$, where $n$ is an integer.

Assume that $n^2$ is divisible by $3$, but that $n$ is not divisible by $3$. An integer not divisible by $3$ has the form

$$n=3k+1 \quad\text{or}\quad n=3k+2$$

for some integer $k$.

In the first case,

$$(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1.$$

In the second case,

$$(3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1.$$

In both cases $n^2$ leaves remainder $1$ when divided by $3$, so it is not divisible by $3$. This contradicts the given information. Therefore $n$ is divisible by $3$.

Here the assumption must include the given condition and the negation of the conclusion. This is the standard approach to proving an implication $A\Rightarrow B$ by contradiction: assume $A$ and $\neg B$.

Example 5: infinitely many primes

Prove that there are infinitely many prime numbers.

Assume, for contradiction, that there are only finitely many primes. List all of them:

$$p_1,p_2,\ldots,p_n.$$

Form the integer

$$N=p_1p_2\cdots p_n+1.$$

For each listed prime $p_i$, division gives

$$N=p_i\left(\prod_{j\ne i}p_j\right)+1.$$

Therefore $N$ leaves remainder $1$ when divided by every prime on the list. Since $N>1$, it is either prime or has a prime factor. In either case, there is a prime not on the supposedly complete list. This is a contradiction. Therefore there are infinitely many primes.

It is not necessary to claim that $N$ itself is prime. For the list $2,3,5,7,11,13$, the product plus $1$ is $30031=59\times509$. What matters is that none of its prime factors is on the original list.

Choosing contradiction

Proof by contradiction is especially effective when:

• the negation gives a concrete algebraic form, such as writing a rational number as $a/b$
• the claim says that something does not exist
• assuming a finite list lets you construct an object outside that list
• the desired conclusion is awkward to reach directly, but its negation strongly restricts the possibilities

It is not automatically the best method. If a short direct chain establishes the result, proof by deduction is usually clearer.

Common misconceptions

Checking examples is not a contradiction proof

Testing $n=1,2,3,4$ may suggest a pattern, but it says nothing about every later integer. A proof needs a general argument using an arbitrary integer.

A surprising result is not necessarily impossible

A contradiction must violate a definition, a given condition or an established fact. Reaching a negative value, a fraction or an irrational number is not contradictory unless the context forbids it.

Do not assume what you are trying to prove

To prove that $\sqrt{2}$ is irrational, begin by assuming it is rational. Starting with “let $\sqrt{2}$ be irrational” is circular and proves nothing.

Name the contradiction

Do not end with only “contradiction”. State the conflict, such as “both $a$ and $b$ are even, contradicting that $a/b$ is in lowest terms”.

Self-check

1. Write the negation of “for every real $x$, $x^2+1>0$”.
2. Prove by contradiction that there is no smallest positive real number.
3. Let $x$ be irrational and $r$ be a non-zero rational number. Prove that $rx$ is irrational.
4. A student trying to prove that there are infinitely many primes says that $p_1p_2\cdots p_n+1$ must be prime. Explain the error and repair the argument.

Answers

1. There exists a real $x$ such that $x^2+1\leq0$.
2. Suppose $s$ is the smallest positive real number. Then $s/2$ is positive and $s/2<s$, contradicting the supposed minimality of $s$. Hence no smallest positive real number exists.
3. Suppose $rx$ is rational, say $rx=q$. Since $r\ne0$, $x=q/r$. The quotient of rational numbers with non-zero denominator is rational, contradicting that $x$ is irrational. Therefore $rx$ is irrational.
4. The constructed number need not be prime. However, it is greater than $1$, so it has a prime factor. No listed prime divides it because division by each leaves remainder $1$. Its prime factor is therefore absent from the allegedly complete list, which gives the required contradiction.

Next steps

Practise deciding when a direct argument is more natural in proof by deduction and exhaustion. Then learn how one carefully chosen case can disprove a universal claim in disproof by counterexample. For more exact-number arguments, revisit surds.