Mp3 - Proof by contradiction | OCR A-Level Mathematics B (MEI)

Contradiction turns a temporary assumption into a reason it cannot be true. You will prove that $\sqrt{2}$ is irrational and that the primes never run out, then use a supplied definition to tackle an unfamiliar relationship between lengths. In each argument, the essential step is to identify the exact statements that conflict.

Assume the opposite and find the conflict

Could a sufficiently tiny ruler unit measure both a square's side and its diagonal exactly, using a whole number of units each time? If the side is $1$ , Pythagoras gives a diagonal of $\sqrt{2}$ . A decimal approximation such as $1.414213562$ does not decide whether the two lengths can share such a unit. We will settle the question by ruling out an assumed relationship.

You already know

A rational number is a ratio of integers with a nonzero denominator. An irrational number is real but has no such ratio. Pythagoras gives $d^2=1^2+1^2=2$ for the diagonal $d$ of a unit square, so $d=\sqrt{2}$ .

The exact geometry makes the question precise; measuring a picture more accurately would not prove an exact relationship.

[DIAGRAM: asset_name: A side and diagonal with a proposed common unit; asset_slug: h640_proof_square_diagonal; caption: A unit square has side 1 and diagonal square root of two; description: An equal-scale square has bottom and right side lengths 1, a sage diagonal d and a right-angle marker at bottom right. Alongside it, d squared equals 1 squared plus 1 squared equals 2 and d equals square root of two. Text asks whether a common unit can measure the side and diagonal exactly.]
A unit square has side 1 and diagonal square root of two

Here is the central idea in a simpler setting. If $N$ were the largest integer, the integer $N+1$ would be larger. Those statements cannot both hold, so the assumed largest integer does not exist.

Proof by contradiction

Assume the negation of the statement you want to establish. Deduce a conflict with a known fact or the assumption itself, then reject the temporary assumption and conclude the required statement. The conflict must be logically impossible, not merely unexpected.

Take care with the negation. “Not every member has the property” means “at least one lacks it”; it does not mean “every member lacks it”. To oppose a claim that no object exists, assume at least one such object exists.

Worked example 1: defeating a supposed minimum

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

Plan. Assume a smallest candidate and halve it, checking that the new number is still allowed.

Let $r=a/b>0$ be the alleged smallest positive rational, where $a,b$ are integers and $b\ne0$ .

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

Why this step? A smaller number defeats the minimum only if it remains positive and rational.

Answer. The existence of $s$ contradicts the minimality of $r$ . No smallest positive rational exists.

Check. A proposed $r=1/30$ is defeated by $s=1/60$ .

For example 2, change only the lower boundary to $3$ . Halving the candidate might drop below the boundary, so choose the midpoint between candidate and boundary instead.

Worked example 2: keeping the constructed number in its domain

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

Plan. Assume a smallest candidate and find a rational strictly between it and $3$ .

Suppose $r>3$ is the smallest such rational. Set $s=(r+3)/2$ , which is rational. Then

\begin{aligned} s-3&=\frac{r-3}{2}>0 && \text{the new number exceeds }3 \\ r-s&=\frac{r-3}{2}>0 && \text{the new number is smaller} \end{aligned}

Why this step? The two positive differences establish both required comparisons without relying on a particular candidate.

Answer. $3<s<r$ contradicts the assumed minimum. No smallest rational above $3$ exists.

Check. If $r=7/2$ , then $s=13/4$ , and $3<13/4<7/2$ .

The proof method is not on the formula sheet. You supply the assumption, the justified construction and the conflict.

Watch out

Wrong: “The new number looks smaller, so there is a contradiction.”

Right: establish that it is both smaller and in the original domain. A number below the allowed lower boundary cannot defeat a minimum within that domain.

Use the same construction at a different boundary.

Why the square root of two is irrational

Assuming a rational square root gives an exact fraction to work with. Choose it in lowest terms so that forcing a common factor will create a genuine contradiction.

We need one parity result first. An odd integer has the form $a=2k+1$ , so

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

is odd. Hence if an integer's square is even, the integer itself is even: an odd input has just been ruled out.

A fraction in lowest terms

A fraction $a/b$ , with integer numerator and nonzero integer denominator, is in lowest terms if $a$ and $b$ are coprime: they have no common positive divisor other than $1$ . Any rational number can be represented this way. For example, $2/4$ is not in lowest terms, whereas $1/2$ is.

The root $\sqrt{2}$ means the positive number whose square is $2$ . Its defining equation gives the exact starting point for the argument.

Worked example 3: no reduced fraction can represent the square root

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

Plan. Assume a lowest-terms fraction, square it, then use the parity result on both entries.

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

\begin{aligned} a^2&=2b^2 && \text{square and clear the denominator} \\ a&=2k\quad(k\in\mathbb Z) && \text{even square means even integer} \\ 4k^2&=2b^2 && \text{substitute the even form} \\ b^2&=2k^2 && \text{simplify} \end{aligned}

Thus $b$ is even too, so $a$ and $b$ share the factor $2$ .

Why this step? The common factor conflicts specifically with “in lowest terms”, not with the definition of a fraction.

Answer. The rational assumption is impossible. Therefore $\sqrt{2}$ is irrational.

Check. An unreduced fraction could have two even entries without conflict. The chosen coprime condition is doing essential work.

Example 4 changes only the rational multiplier of $\sqrt{2}$ . Its nonzero value lets you transfer the assumed rationality back to the square root.

Worked example 4: transferring rationality backwards

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

Plan. Assume the product rational and divide by $2$ to contradict the established result.

Suppose $t=2\sqrt{2}=a/b$ , for integers $a,b$ , with $b\ne0$ . Then

\begin{aligned} \sqrt{2}&=\frac t2 && \text{divide by nonzero }2 \\ &=\frac a{2b} && \text{an integer ratio} \end{aligned}

Since $2b\ne0$ , this is a rational representation of $\sqrt{2}$ , which is impossible.

Why this step? An alleged rational product has forced a known irrational number to be rational.

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

Check. This argument would fail for a zero multiplier: $0\sqrt{2}=0$ is rational and division by zero is unavailable.

The result answers part of the opening puzzle: the unit square's diagonal is not a fraction at all. An exact parity argument settles something no finite decimal search can settle. Neither the irrationality proof nor this parity result is supplied on the formula sheet.

Watch out

An even square implies an even integer because we ruled out the odd case. Do not generalise that step to every divisor: $2^2$ is divisible by $4$ , although $2$ is not. A new divisibility step needs its own justification.

Use a new multiplier and state exactly which established fact is contradicted.

Why a finite prime list cannot be complete

The primes never run out, and you can prove that without a formula generating prime after prime. A construction that guarantees a new prime divisor is enough.

Remember the distinction between a number and its prime divisors. Surprisingly,

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

is composite. Its prime divisors $59$ and $509$ are new relative to that list, which is the property the proof needs.

You already know

Every integer $N>1$ has a prime divisor. Its smallest divisor greater than $1$ must be prime: otherwise a smaller factor greater than $1$ would divide $N$ . Also, a divisor of two integers divides their difference.

Use a concrete list first, then remove the restriction on how long the list may be.

Worked example 5: a prime divisor outside a chosen list

Question. Construct an integer with a prime divisor outside the list $2,3,7$ .

Plan. Multiply the entries, add $1$ , and inspect division by the listed primes.

\begin{aligned} P&=2\times3\times7=42 && \text{all listed primes divide }P \\ N&=P+1=43 && \text{construct the new number} \\ N-P&=1 && \text{compare} \end{aligned}

No listed prime can divide both $P$ and $N$ , because that would make it a divisor of $1$ .

Why this step? The difference argument excludes the whole list in one move.

Answer. $N=43>1$ has a prime divisor outside $2,3,7$ .

Check. Here $43$ itself is prime: the possible prime divisors up to $\sqrt{43}$ are $2,3,5$ , and none divides it.

In example 6 the list length becomes arbitrary. The same reasoning now rejects a list claimed to contain every prime.

Worked example 6: the general infinity argument

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

Plan. Assume a complete finite prime list, then construct a prime divisor that cannot appear on it.

Suppose every prime appears in the finite list $p_1,\ldots,p_k$ . It is nonempty because $2$ is prime. Define

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{definition of }P \\ N-P&=1 && \text{definition of }N \end{aligned}

If $p_i$ divided $N$ , it would divide $1$ , which is impossible. Yet $N>1$ has a prime divisor $q$ . Thus $q$ is outside the allegedly complete list.

Why this step? Prime-divisor existence works even when $N$ is composite, so the construction does not need an unsupported claim that $N$ is prime.

Answer. The assumption of a complete finite list gives a contradiction. There are infinitely many primes.

Check. For the six-prime construction above, the composite number $30031$ still supplies prime divisors absent from its list.

This argument is not printed on the formula sheet. Its insight is to use the supposed complete list to make the object that defeats its completeness.

Watch out

Wrong: “Adding $1$ to the product makes a prime.”

Right: the constructed integer has a prime divisor that is not in the list. The composite value $30031$ shows why the distinction matters.

A new finite list gives a useful test of that distinction.

Contradiction with a newly defined relationship

A supplied definition lets you reason about an unfamiliar word without learning a new theorem. Translate the definition into equations, then use facts you already understand.

Rational subtraction is one useful fact: for $r=a/b$ and $t=c/d$ , with integer entries and nonzero $b,d$ ,

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

is rational. The numerator and denominator are integers, and the denominator is nonzero. This also explains why subtracting an assumed rational value from a rational constant can expose a contradiction with irrationality.

Rational ratios and differences

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

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

Not in the formula sheet: learn it.

Now read the new definition closely. It makes an existence claim, not a claim that every possible unit works.

Commensurable lengths

Two positive lengths are commensurable if there is a positive length $d$ such that both lengths are positive integer multiples of $d$ . For example, lengths $2$ and $3$ in the same unit are commensurable: choose $d=1$ . Their common unit need not be one of the two lengths.

To prove two lengths are not commensurable, assume that at least one suitable $d$ exists and follow its consequences. The integer counts and positivity are part of the definition, not optional details.

Worked example 7: side and diagonal of the unit square

Question. Prove that lengths $1$ and $\sqrt{2}$ in the same unit are not commensurable.

Plan. Assume a common positive length, write its two integer counts and eliminate it.

Suppose $1=ad$ and $\sqrt{2}=bd$ , where $a,b$ are positive integers and $d>0$ . Then

\begin{aligned} d&=\frac1a && \text{since }a>0 \\ \sqrt{2}&=\frac ba && \text{substitute in the second equation} \end{aligned}

The ratio $b/a$ is rational because $a,b$ are integers and $a\ne0$ . This contradicts the irrationality of $\sqrt{2}$ .

Why this step? Eliminating the unfamiliar common unit leaves the familiar impossible rational representation.

Answer. No such common positive length exists; the side and diagonal are not commensurable.

Check. Multiplying the ratio $b/a$ by the first length $1$ recovers the second length that the assumption requires.

Example 8 changes only the rational length from $1$ to $2$ . The same elimination must preserve that factor.

Worked example 8: a different rational length

Question. Prove that lengths $2$ and $\sqrt{2}$ are not commensurable.

Plan. Use the definition with the new length and isolate a rational ratio for $\sqrt{2}$ .

Suppose $2=ad$ and $\sqrt{2}=bd$ , where $a,b$ are positive integers and $d>0$ . Then

\begin{aligned} d&=\frac2a && \text{divide by positive }a \\ \sqrt{2}&=\frac{2b}{a} && \text{eliminate }d \end{aligned}

The last expression is rational, contradicting the established irrationality of $\sqrt{2}$ .

Why this step? The factor $2$ changes the numerator, but it remains an integer and the denominator remains nonzero.

Answer. The lengths $2$ and $\sqrt{2}$ are not commensurable.

Check. Substituting $d=2/a$ into $ad$ gives $2$ , so the elimination respects the first length.

This settles the opening ruler puzzle: even an arbitrarily tiny common unit cannot give integer counts for both a square's side and diagonal. Their ratio would have to be rational. The supplied definition led you to the same obstruction as the fraction proof.

Problem-solving

For an unfamiliar definition, identify exactly what exists, translate its conditions into equations, and check every cancellation. Here $a>0$ and $d>0$ make division legitimate.

Keep the supplied definition and change the rational length once again.

Quick Recap

Contradiction begins with the negation and ends by naming an impossible conflict.
The $\sqrt{2}$ proof needs a lowest-terms fraction and a justified parity step.
A finite prime list produces a new prime divisor; the constructed number need not be prime.
A new definition becomes usable when you translate its exact conditions into familiar equations.

No common positive ruler unit can measure the unit square's side and diagonal in integer counts: their ratio would make $\sqrt{2}$ rational, which the parity proof rules out.

Last Accessed

Pure Mathematics

Statistics

Mechanics

Mp3 - 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

Contradiction with a newly defined relationship

Quick Recap

Learn faster with Nova