Maths › Proof › Disproof and proof by contradiction

Disproof and proof by contradiction

To kill a mathematical claim you need exactly one well-chosen example. To prove one, sometimes the strongest move is judo: assume the claim is false, follow the consequences until mathematics breaks, and conclude it must have been true all along.

Year 12-13EDEXCEL 9MA0 1.1

Builds on The structure of proof: deduction and exhaustion.

IN THIS TOPIC

  • Disprove statements by finding a single counter example.
  • Reproduce the contradiction proofs of the irrationality of √2 and the infinity of primes.
  • Apply proof by contradiction to unfamiliar statements.

WHAT YOU PROBABLY THINK

To disprove a claim you must show it fails every time.

One counter example is enough

A universal claim says something about every case, so a single case where it fails destroys it entirely. That is disproof by counter example, and it is the one place in this unit where checking numbers is the whole job. The skill is choosing where to look: boundary values, negatives, zero, and numbers with awkward factorisations all earn their keep.

WORKED EXAMPLE

A prime-generating formula, allegedly

Show that the statement “n2 − n + 1 is a prime number for all values of n” is untrue.

Try n = 5: 25 − 5 + 1 = 21 = 3 × 7, which is not prime.

One counter example, clearly evaluated and clearly factorised, and the disproof is complete. ∎

The formula's early record (3, 7, 13 for n = 2, 3, 4) is why the lie above is tempting, and exactly why it is a lie: a good run of examples is not a proof.

The values of n squared minus n plus 1 look prime, until n equals 5 delivers 21, which factorises as 3 times 7: one counter example ends the claimn = 23n = 37n = 413n = 52121 = 3 × 7prime, prime, prime… and then nota claim about all n dies on a single counter example
FIG. 1The formula's record, computed: prime at n = 2, 3 and 4, then 21 = 3 × 7 at n = 5. The claim about all n does not survive the first composite value.

Proof by contradiction

The recipe for proof by contradiction: assume the statement is false, reason correctly until something impossible appears, and conclude the statement was truesuppose notreason correctlyimpossibilityso the statement is truevalid steps cannot create absurdity,so the assumption takes the blamethree moves: they prove root 2 irrational and the primes endless
FIG. 2The whole method in one line of boxes: assume the opposite, reason soundly, hit an impossibility, and the original statement is forced to be true.

Some truths resist direct attack. Proof by contradiction comes at them backwards: assume the statement is false, reason correctly from that assumption, and arrive at something impossible, a contradiction. Correct reasoning cannot turn a truth into an absurdity, so the assumption was wrong, and the original statement stands. The two classics below are named by the specification and must be reproducible on demand.

WORKED EXAMPLE

√2 is irrational

Prove that √2 cannot be written as a fraction of integers.

Assume it can: √2 = a/b with a, b integers sharing no common factor (any fraction can be put in this lowest form).

Squaring: 2 = a2/b2, so a2 = 2b2. Then a2 is even, and since odd × odd is odd, a itself must be even: a = 2c.

Substitute: (2c)2 = 2b2 gives b2 = 2c2, so b is even too. But now a and b share the factor 2, contradicting the lowest-form assumption. ∎

Every step was legitimate, so the only faulty ingredient was the opening assumption: no such fraction exists. Note how last lesson's odd-times-odd result quietly powered the middle step.

WORKED EXAMPLE

There are infinitely many primes

Prove that the list of primes never ends.

Assume it does: let the complete list be p1, p2, …, pn, and consider N = p1p2…pn + 1.

Divide N by any prime on the list and the remainder is 1, so no listed prime divides N. But every integer above 1 has at least one prime factor, so N has a prime factor missing from the complete list: contradiction. ∎

A common slip is claiming N itself must be prime. Not so: 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30 031 = 59 × 509. The proof only needs N's prime factors to be new, and that is what the remainder argument delivers.

Making it yours

The examiners' phrase is “application to unfamiliar proofs”: the two classics are the templates, and the technique transfers whenever assuming the opposite gives you something concrete to work with. The recipe is always the same three sentences: assume the negation, derive an impossibility, conclude the statement.

YOUR TURN

No largest even number

Prove by contradiction that there is no largest even number, before opening the working.

Show the working

Assume there is one: call it E, an even number with no even number larger.

Then E + 2 is even, and E + 2 > E: an even number larger than the largest even number. Contradiction, so no largest even number exists. ∎

Small as it is, this has the full anatomy: the negation gave us a concrete object, E, and the object destroyed itself.

TRY IT UNSEEN

A logarithm that cannot be a fraction

Prove by contradiction that log2 3 is irrational.

Show the working

Assume log2 3 = a/b for positive integers a and b. Then 2a/b = 3, so 2a = 3b.

The left side is even (a ≥ 1); the right side is odd, being a product of odd factors. An even number cannot equal an odd one: contradiction. ∎

Unfamiliar statement, familiar machinery: the negation handed us an equation between integers, and parity finished it, just as it finished √2.

THE EXAM BIT

  • A disproof needs one counter example, fully shown: state the value, evaluate the expression, and show why the result breaks the claim (factorise it, or exhibit the failure).
  • Open every contradiction proof by stating the assumption in full: "assume √2 is rational, so √2 = a/b in lowest terms". The lowest-terms clause is not decoration; the contradiction lands on it.
  • The two named proofs, irrationality of √2 and infinitude of primes, are quotable questions. Learn them as arguments, not scripts: markers follow the logic, not the wording.
  • In the primes proof, do not claim N is prime; claim its prime factors cannot be on the list. The 30 031 example is the standard trap.
  • Close the loop explicitly: "this contradicts …, so the assumption is false and the statement is true". The final sentence carries a mark of its own.

CHECK YOURSELF

Prove by contradiction that there are no positive integers a and b with 21a + 14b = 1.

Show a hint

Look for a common factor on the left that the right cannot match.

Show the answer

Assume such integers exist: 21a + 14b = 1 with a, b positive integers.

The left side is 7(3a + 2b), a multiple of 7. So 1 would be a multiple of 7, which is false: contradiction. ∎

So no such integers exist. The negation produced an equation, and one common factor demolished it: the whole craft is spotting which impossibility the assumption walks into.

One counter example kills a universal claim stone dead.

To prove by contradiction: assume the opposite, break mathematics, conclude.

CHECK YOUR PROGRESS

Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.

  • Disprove statements by finding a single counter example.
  • Reproduce the contradiction proofs of the irrationality of √2 and the infinity of primes.
  • Apply proof by contradiction to unfamiliar statements.

No animated video for this topic yet; these notes stand alone.