1.01d - Proof by contradiction | OCR A-Level Mathematics A

Some claims become easier when you temporarily assume their opposite. Learn to turn that assumption into a precise conflict, including the proofs that $\sqrt{2}$ is irrational and that there are infinitely many primes. You will then use familiar rational-number properties to build fresh contradiction arguments.

Assume the opposite and find the conflict

Can the diagonal of a square with side length $1$ equal a fraction, perhaps with an enormous denominator? Pythagoras gives its length as $\sqrt{2}$ , approximately $1.414213562$ . No matter how many digits you calculate, a decimal display cannot settle whether an exact fractional representation exists.

You already know

A rational number is $a/b$ for integers $a,b$ , with $b\ne0$ . An irrational number is real but has no such representation. Pythagoras gives the square of a right-angled triangle's hypotenuse as the sum of the squares of its other sides.

The picture identifies the exact length. The proof must decide what kind of number that length is.

[DIAGRAM: asset_name: The diagonal of a unit square; asset_slug: h240_proof_square_diagonal; caption: A unit square has diagonal length square root of two; description: An equal-scale square has bottom and right side lengths 1, a sage diagonal d from bottom left to top right and a right-angle marker at bottom right. Alongside it, d squared equals 1 squared plus 1 squared equals 2, hence d equals square root of two. The question asks whether this diagonal can be a ratio of integers.]
A unit square has diagonal length square root of two

Before tackling that question, practise the logic on a simpler claim. Suppose there were a largest integer $N$ . Then $N+1$ would be a larger integer, contradicting the very meaning of “largest”. The opposite assumption has defeated itself.

Proof by contradiction

A proof by contradiction assumes the negation of the required claim, derives a conflict with an established fact or the assumptions, and concludes that the temporary assumption is false. A surprising consequence is not enough: identify two statements that cannot both hold.

Negate the whole claim carefully. The opposite of “every member has a property” is “at least one member lacks it”. The opposite of “no smallest positive rational exists” is “a smallest positive rational exists”, not “every rational is smallest”.

Worked example 1: no smallest positive rational

Question. Prove by contradiction that there is no smallest positive rational number.

Plan. Assume a smallest one exists and construct a smaller positive rational.

Suppose $r$ is the smallest positive rational. Since $r=a/b>0$ for integers $a,b$ ,

\begin{aligned} \frac r2&=\frac a{2b} && \text{still rational, since }2b\ne0 \\ 0&<\frac r2<r && \text{since }r>0 \end{aligned}

Why this step? The competing number must remain inside the positive rational domain.

Answer. $r/2$ contradicts the supposed minimality of $r$ . Therefore no smallest positive rational number exists.

Check. If a candidate were $1/100$ , then $1/200$ would be a smaller positive rational.

Example 2 changes only the lower boundary from $0$ to $1$ . Dividing the candidate by $2$ could now leave the allowed domain, so use its midpoint with the boundary.

Worked example 2: rational numbers above a boundary

Question. Prove that there is no smallest rational number greater than $1$ .

Plan. Assume a smallest candidate and construct a rational strictly between it and $1$ .

Suppose $r>1$ is the smallest such rational, and put $s=(r+1)/2$ . It is rational because sums and quotients by nonzero integers preserve rationality. Also,

\begin{aligned} s-1&=\frac{r-1}{2}>0 && \text{so }s>1 \\ r-s&=\frac{r-1}{2}>0 && \text{so }s<r \end{aligned}

Why this step? Both differences establish that the new candidate is allowed and is smaller.

Answer. $1<s<r$ contradicts the minimality of $r$ , so no smallest rational above $1$ exists.

Check. At a proposed $r=3/2$ , the construction gives $s=5/4$ , strictly between $1$ and $3/2$ .

The method itself is not supplied on the formula sheet. Its conclusion must name the conflict, rather than simply append the word “contradiction”.

Watch out

Wrong: “The opposite of ‘every value works’ is ‘every value fails’.”

Right: the opposite is “at least one value fails”. Negating more than the claim allows can make an argument invalid.

Try the midpoint construction with a new boundary.

Why the square root of two is irrational

To rule out every fraction at once, suppose the exact square root has a fraction in lowest terms. The contradiction will be that this supposedly reduced fraction still has a common factor.

First justify the parity step. If an integer $a=2k+1$ is odd, then

a^2=4k^2+4k+1=2(2k^2+2k)+1

is odd. Since every integer is even or odd, an even square must therefore come from an even integer.

Coprime integers

Two integers are coprime when their only common positive divisor is $1$ . A fraction in lowest terms has a coprime numerator and denominator. For example, $3/4$ is reduced; $2/4$ is not. Every rational number can be reduced to lowest terms.

The positive root $\sqrt{2}$ has square $2$ . No further surd manipulation is needed for its proof.

Worked example 3: the irrationality of the square root of two

Question. Prove by contradiction that $\sqrt{2}$ is irrational.

Plan. Assume a reduced rational representation, square it and use parity to force a common factor.

Suppose $\sqrt{2}=a/b$ , where $a,b$ are coprime positive integers. Then

\begin{aligned} a^2&=2b^2 && \text{square and multiply by }b^2 \\ a&=2k\quad(k\in\mathbb Z) && \text{an even square gives even }a \\ 4k^2&=2b^2 && \text{substitute }a=2k \\ b^2&=2k^2 && \text{divide by }2 \end{aligned}

Thus $b$ is even as well. Both $a$ and $b$ have the common factor $2$ .

Why this step? The lowest-terms assumption makes the common factor impossible, so it contradicts the starting representation.

Answer. The assumed rational representation cannot exist. Hence $\sqrt{2}$ is irrational.

Check. The argument uses exact equalities and arbitrary integers; it does not rely on the number of decimal places displayed.

Example 4 changes only the multiplier of the established irrational number. You can now use the result rather than repeat the parity proof.

Worked example 4: a nonzero rational multiple

Question. Prove by contradiction that $3\sqrt{2}$ is irrational.

Plan. Assume the product is rational, then divide by its nonzero rational multiplier.

Suppose $t=3\sqrt{2}$ is rational. Write $t=a/b$ , with integers $a,b$ and $b\ne0$ . Then

\begin{aligned} \sqrt{2}&=\frac t3 && \text{divide by nonzero }3 \\ &=\frac a{3b} && \text{substitute the rational form} \end{aligned}

The last expression is rational: $a,3b$ are integers and $3b\ne0$ . This contradicts the irrationality just proved.

Why this step? Producing a rational representation of $\sqrt{2}$ names an established fact that the assumption would violate.

Answer. $3\sqrt{2}$ is irrational.

Check. The coefficient must be nonzero: $0\sqrt{2}=0$ is rational, so the same reasoning could not divide by it.

This answers the opening question: a unit square's diagonal cannot be any ratio of integers, however large the denominator. The irrationality result and parity argument are not supplied on the formula sheet.

Watch out

Both numerator and denominator being even is a contradiction only if you chose the fraction in lowest terms. The fraction $2/4$ has two even entries without any contradiction. Also, $a^2$ divisible by $4$ need not make $a$ divisible by $4$ : $2^2=4$ , but $2$ is not a multiple of $4$ .

Change the nonzero multiplier and identify the same precise conflict.

Why a finite prime list cannot be complete

Any finite list of primes can be beaten by constructing an integer with a prime divisor outside it. The constructed integer need not itself be prime.

For a striking example,

2\times3\times5\times7\times11\times13+1=30031=59\times509

The “multiply and add one” construction does not reliably produce a prime. It reliably prevents every listed prime from dividing the new integer.

You already know

If a positive integer $d$ divides two integers, it divides their difference. Every integer $N>1$ has a prime divisor: its smallest divisor greater than $1$ must be prime, or a smaller proper factor would also divide $N$ .

Begin with a short list so the construction is visible before making the list arbitrary.

Worked example 5: escaping a particular list

Question. Use the primes $2,3,5$ to construct an integer having a prime divisor outside this list.

Plan. Multiply the listed primes and add $1$ , then compare the new integer with the product.

\begin{aligned} P&=2\times3\times5=30 && \text{multiply the list} \\ N&=P+1=31 && \text{add }1 \\ N-P&=1 && \text{compare the two integers} \end{aligned}

Each listed prime divides $P$ . If it also divided $N$ , it would divide $1$ , which is impossible.

Why this step? The difference excludes every listed prime, even without deciding whether $N$ itself is prime.

Answer. $N=31>1$ has a prime divisor, and that divisor is not $2,3$ or $5$ .

Check. Here $31$ is itself prime: none of $2,3,5$ , the primes at most $\sqrt{31}$ , divides it.

Example 6 changes only the size of the list: instead of three named primes, allow an arbitrary finite list that is claimed to contain every prime.

Worked example 6: infinitely many primes

Question. Prove by contradiction that there are infinitely many primes.

Plan. Assume a complete finite list and apply the same construction to force a missing prime divisor.

Suppose all primes are $p_1,p_2,\ldots,p_k$ . The list is nonempty because $2$ is prime. Put

P=p_1p_2\cdots p_k,\qquad N=P+1>1

For any listed $p_i$ ,

\begin{aligned} p_i&\text{ divides }P && \text{it is a factor} \\ N-P&=1 && \text{definition of }N \end{aligned}

Thus $p_i$ cannot divide $N$ : otherwise it divides $1$ . But $N>1$ has a prime divisor $q$ , so $q$ is absent from the supposedly complete list.

Why this step? Prime-divisor existence works whether $N$ is prime or composite; claiming $N$ prime would leave a gap.

Answer. A complete finite list would omit a prime, a contradiction. Therefore there are infinitely many primes.

Check. The earlier value $30031$ is composite, but its prime divisors $59$ and $509$ are both outside its construction list, exactly as required.

The proof is not a formula-sheet result. Its reusable idea is to construct something the assumption says cannot exist.

Watch out

Wrong: “The product of the listed primes plus $1$ is prime.”

Right: it has a prime divisor outside the list. That weaker, justified statement is enough for the contradiction.

Use a different finite list; it need not contain consecutive primes for the construction to work.

Using rational-number assumptions

A contradiction often appears after a simple rearrangement: an alleged rational value would make a known irrational number rational.

The engine is closure under subtraction. If $r=a/b$ and $t=c/d$ , with integer entries and $b,d\ne0$ , then

t-r=\frac{bc-ad}{bd}

is rational because its numerator and nonzero denominator are integers. That explanation is what “rational numbers are closed under subtraction” means.

Subtracting rational numbers

For integers $a,b,c,d$ , with $b,d\ne0$ ,

\frac cd-\frac ab=\frac{bc-ad}{bd}\in\mathbb Q

Not in the formula sheet: learn it.

Consequently, if $r$ is rational and $s$ is irrational, their sum is irrational. If instead $r+s=t$ were rational, then $s=t-r$ would be rational, contradicting the hypothesis about $s$ . Here are two concrete uses of that general argument.

Worked example 7: adding a rational number

Question. Prove that $3+\sqrt{2}$ is irrational.

Plan. Assume the sum rational and isolate $\sqrt{2}$ by subtracting $3$ .

Suppose $t=3+\sqrt{2}$ is rational. Then

\begin{aligned} \sqrt{2}&=t-3 && \text{rearrange} \\ t-3&\in\mathbb Q && \text{subtract rational numbers} \end{aligned}

This would make $\sqrt{2}$ rational, contrary to the established result.

Why this step? Isolating the known irrational number exposes the exact conflict.

Answer. $3+\sqrt{2}$ is irrational.

Check. Reversing the rearrangement recovers $t=3+\sqrt{2}$ ; no division or extra domain assumption was introduced.

Example 8 changes only the sign of the irrational term. Follow the rearrangement carefully rather than changing a sign by memory.

Worked example 8: subtracting an irrational number

Question. Prove that $3-\sqrt{2}$ is irrational.

Plan. Assume a rational value and move the square-root term to the other side.

Suppose $t=3-\sqrt{2}$ is rational. Then

\begin{aligned} \sqrt{2}&=3-t && \text{rearrange} \\ 3-t&\in\mathbb Q && \text{rational subtraction} \end{aligned}

This contradicts the irrationality of $\sqrt{2}$ .

Why this step? The rationality of a difference is independent of which rational number is written first.

Answer. $3-\sqrt{2}$ is irrational.

Check. Substituting $t=3-\sqrt{2}$ into $3-t$ gives $\sqrt{2}$ , confirming the sign.

The hypotheses matter: two irrational numbers can sum to a rational number, as $\sqrt{2}+(-\sqrt{2})=0$ shows. You cannot use rational closure on inputs you have not established as rational.

Exam tip

Finish by naming the incompatible statements: the rearrangement makes $\sqrt{2}$ rational, while its irrationality has been established. “Contradiction” alone does not explain the conflict.

Keep the sign and change the rational constant.

Quick Recap

Negate the claim accurately, then keep all its domain conditions.
The $\sqrt{2}$ proof contradicts a lowest-terms fraction by forcing both entries even.
A product of listed primes plus $1$ has a new prime divisor, even when it is composite.
Rational closure can turn a rearranged assumption into a precise irrationality contradiction.

The unit square's diagonal is $\sqrt{2}$ , and no exact fraction represents it. The parity contradiction rules out every denominator at once.

Last Accessed

Pure Mathematics

Statistics

Mechanics

1.01d - Proof by contradiction

Assume the opposite and find the conflict

Why the square root of two is irrational

Why a finite prime list cannot be complete

Using rational-number assumptions

Quick Recap

Learn faster with Nova