Proof by contradiction

Proof by contradiction

Spec 1.1 · Edexcel International A Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Assume the statement is false, argue logically, and reach something impossible.
  • Write the negation carefully before you start.
  • 2\sqrt2 is irrational: assume pq\frac pq in lowest terms and show both pp and qq are even.
  • There are infinitely many primes: a list of all primes always misses a prime factor of N = (product) + 1.
  • Examples never prove a general statement.

The method

Assume the statement is false and show that this leads to something impossible.

Each step must follow from the one before. The contradiction is the whole point, so state it clearly, for example "this contradicts the assumption that pp and qq have no common factor".

The negation of a statement is true exactly when the original is false. Write it down before you start.

  1. 1

    Assume the negation

    write it down before you start

  2. 2

    Argue logically

    each step follows from the last

  3. 3

    Reach a contradiction

    something impossible

  4. 4

    Conclude

    the assumption is false, so the statement is true

The four stages of a proof by contradiction

Statement

  • For all nn, n2n^2 is even
  • There is no integer with…
  • xx is irrational

Negation

  • There exists an integer nn with n2n^2 odd
  • There is an integer with…
  • xx is rational

What is the negation of "3\sqrt3 is irrational"?

√2 is irrational

Assume 2=pq\sqrt2=\frac pq in lowest terms, then show pp and qq are both even.

Assume 2=pq\sqrt2=\frac{p}{q} where p,qp,q are integers with no common factor and q≠0q\neq0.

Squaring, p2=2q2p^2=2q^2. So p2p^2 is even, and therefore pp is even. Write p=2kp=2k. Then q2=2k2q^2=2k^2, so qq is even.

Now pp and qq share the factor 2. This contradicts the assumption. Therefore 2\sqrt2 is irrational. The same argument works for p\sqrt p for any prime pp.

  1. 1

    Assume

    √2 = p/q in lowest terms

  2. 2

    Square

    p² = 2q², so p is even

  3. 3

    Substitute

    p = 2k gives q² = 2k², so q is even

  4. 4

    Contradiction

    both even, so a common factor 2

Why the proof works

Why is the condition 'no common factor' included in the first line?

Infinitely many primes

Assume a finite list of primes, form N=p1p2⋯pn+1N=p_1p_2\cdots p_n+1, and find a prime factor not in the list.

Dividing NN by any pip_i leaves remainder 1, so no pip_i divides NN. But N>1N>1 has at least one prime factor, and it is not in the list.

This contradicts the assumption that the list contains all the primes.

NN need not itself be prime: with the primes up to 13, N=30031=59×509N=30031=59\times509, and the argument works because 59 and 509 are primes outside the list.

  1. 1

    Assume

    a finite list of all the primes

  2. 2

    Form N

    multiply them all and add 1

  3. 3

    Find a prime factor

    it cannot be any prime on the list

  4. 4

    Contradiction

    so the list was incomplete

The structure of Euclid’s proof

Worked example

Take the primes 2, 3, 5, 7, 11, 13. Form NN and show it is not divisible by any of them.

What does the proof need to say about NN?

Parity and divisibility

Look for a property, such as parity or divisibility, that the assumption forces on both sides of an equation.

Example 1: there are no integers with 14m+21n=114m+21n=1. Assume there are, then 7(2m+3n)=17(2m+3n)=1, so 2m+3n=172m+3n=\frac17, which is not an integer.

Example 2: log⁡23\log_23 is irrational. Assume log⁡23=pq\log_23=\frac{p}{q} with positive integers, so 2p=3q2^p=3^q: even equals odd.

Example 3: x2−y2=2x^2-y^2=2 has no integer solutions. (x−y)(x+y)=2(x-y)(x+y)=2, and the two factors have the same parity, so both are even and the product is a multiple of 4, not 2.

  1. 1

    Assume the opposite

    for example that integers m and n exist

  2. 2

    Factorise or rearrange

    to expose a factor such as 7 or 2

  3. 3

    Compare parity or divisibility

    one side is a multiple, the other is not

  4. 4

    Contradiction

    so the assumption is false and the statement is true

The shape of a parity proof by contradiction.

Fact

  • Even × anything is even
  • Odd × odd is odd
  • Square of odd is odd
  • Square of even is even

Example

  • 2×7=142\times7=14
  • 3×5=153\times5=15
  • 72=497^2=49
  • 62=366^2=36

In Example 3, why is the product (x−y)(x+y)(x-y)(x+y) a multiple of 4 when both factors are even?

Using a known irrational

Assume the number is rational, rearrange to make 2\sqrt2 equal to a rational expression, and contradict its irrationality.

You may use the fact that 2\sqrt2 is irrational. To show 2+3\sqrt2+\sqrt3 is irrational, assume it equals rr with rr rational. Isolate a root and square: 3=r−2\sqrt3=r-\sqrt2, so 3=r2−2r2+23=r^2-2r\sqrt2+2 and 2=r2−12r\sqrt2=\frac{r^2-1}{2r}.

The right-hand side is rational, which contradicts the irrationality of 2\sqrt2.

Rationals are closed under addition, subtraction, multiplication and division by a non-zero number.

  1. 1

    Assume rational

    √2 + √3 = r with r rational

  2. 2

    Isolate a root

    √3 = r − √2

  3. 3

    Square both sides

    3 = r² − 2r√2 + 2

  4. 4

    Make √2 the subject

    √2 = (r² − 1) / 2r, which is rational

  5. 5

    Contradiction

    √2 is irrational, so √2 + √3 is irrational

Proving a sum of surds irrational.
  • rational ±\pm rationalrational
  • rational ×\times rationalrational
  • rational ÷\div non-zero rationalrational

Worked example

Prove that 2+3\sqrt2+\sqrt3 is irrational.

Why is r2−12r\frac{r^2-1}{2r} rational when rr is rational?

Writing a proof

Assume, give each step with a reason, name the contradiction, then state what is proved.

Do not test examples: a few numerical cases never prove a general statement.

A contradiction can be with the assumption itself, with a given fact, or with a basic truth such as "even = odd". If you reach something that is merely unlikely, it is not a contradiction.

  1. 1

    Assume

    state the negation

  2. 2

    Steps with reasons

    each line follows from the last

  3. 3

    This contradicts

    name what is contradicted

  4. 4

    Hence

    state what has been proved

Layout of a written proof

Does checking that a statement is true for n=1,2,3,4,5n=1,2,3,4,5 prove it for all nn?

Try an exam question

Prove by contradiction that 3\sqrt3 is irrational. You may use the fact that if p2p^2 is a multiple of 3 then pp is a multiple of 3.

[5 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which assumption should the proof begin with?

1 mark, marked against the mark scheme

Revision notes