Proof by contradiction

Proof by contradiction

Spec 1.1 · Edexcel A-Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Assume the opposite of what you want to prove, then reach a contradiction.
  • The assumption must be the faulty step, so the original statement is true. Always write a concluding sentence.
  • A rational number is ab\frac ab with integers a,ba,b, b≠0b\ne0; assume it is in lowest terms.
  • If a2a^2 is even then aa is even, because an odd number squared is odd.
  • Negate carefully: the opposite of "no integers exist" is "there exist integers".

The method

Assume the opposite, work logically to something impossible, then conclude the assumption is false so the statement is true.

In proof by contradiction you assume the opposite of what you want to prove, then use correct steps to reach something impossible: a contradiction.

Every step was valid, so the faulty item must be the assumption, and the original statement is true.

  1. State the assumption clearly, such as "Assume 2\sqrt2 is rational".
  2. Work logically from it.
  3. Reach a contradiction, such as a number that is both even and odd.
  4. Conclude: "this is a contradiction, so the assumption is false".
  1. 1

    Assume the opposite

    of what you want to prove

  2. 2

    Work logically

    every step must be valid

  3. 3

    Reach a contradiction

    something impossible

  4. 4

    Conclude

    the assumption is false, so the statement is true

Proof by contradiction

To prove 3\sqrt3 is irrational by contradiction, what do you assume first?

Rational and irrational numbers

A rational number is ab\frac ab in lowest terms. Contradiction proofs about irrationals use this and facts about even and odd squares.

A rational number can be written as ab\frac ab with a,ba,b integers and b≠0b\ne0. An irrational number cannot.

Any rational number can be written in lowest terms, where aa and bb share no factor other than 1. Contradiction proofs about irrationals rely on this, so assume it at the start. Without it, "both even" is not a contradiction.

If a2a^2 is even then aa is even.

The same idea works for multiples of 3: if a=3k±1a=3k\pm1 then a2=3(3k2±2k)+1a^2=3(3k^2\pm2k)+1 is not a multiple of 3.

00.511.522.533.544.555.561/2 (rational)0.75 (rational)√2 (irrational)π (irrational)5 (rational)

Rational

Written as:
ab\frac ab with integers, b≠0b\ne0
Examples:
12\frac12, 0.75, 5

Irrational

Written as:
cannot be written as ab\frac ab
Examples:
2\sqrt2, π\pi

Worked example

Show that if a2a^2 is even then aa is even.

Why must ab\frac ab be assumed to be in lowest terms?

The irrationality of root 2

Assume 2=ab\sqrt2=\frac ab in lowest terms. Both aa and bb turn out even, contradicting lowest terms.

Assume 2=ab\sqrt2=\frac ab with a,ba,b integers in lowest terms.

Square: 2=a2b22=\frac{a^2}{b^2}, so a2=2b2a^2=2b^2. Hence a2a^2 is even, so aa is even. Write a=2ka=2k.

Then 4k2=2b24k^2=2b^2, so b2=2k2b^2=2k^2, which is even, so bb is even.

Now aa and bb are both even, so they share the factor 2. This contradicts lowest terms. Hence 2\sqrt2 is irrational.

The same pattern proves 3\sqrt3 irrational, using multiples of 3.

  1. 1

    Assume 2=ab\sqrt2=\frac ab

    in lowest terms

  2. 2

    a2=2b2a^2=2b^2

    so a2a^2 is even

  3. 3

    aa is even

    write a=2ka=2k

  4. 4

    b2=2k2b^2=2k^2

    so bb is even

  5. 5

    Contradiction

    both even, so not in lowest terms

The chain of the proof

In the proof, what is the contradiction?

The infinity of primes

Assume a finite list of primes, multiply them and add 1. The result gives a prime not in the list.

Assume there are finitely many primes p1,p2,…,pnp_1,p_2,\ldots,p_n.

Let N=p1p2⋯pn+1N=p_1p_2\cdots p_n+1. Dividing NN by any pip_i leaves remainder 1, so no pip_i divides NN.

Either NN is prime, or it has a prime factor. In both cases there is a prime not in the list. This contradicts the assumption that the list held all primes, so there are infinitely many primes.

NN need not be prime itself. Its factors are new primes.

  1. 1

    Assume

    a finite list of all primes

  2. 2

    Form N

    the product of the list, plus 1

  3. 3

    Remainder 1

    no prime in the list divides N

  4. 4

    New prime

    N or a prime factor of N is not in the list: contradiction

The argument

Worked example

Take the first six primes 2, 3, 5, 7, 11, 13. Is N=2×3×5×7×11×13+1N=2\times3\times5\times7\times11\times13+1 prime?

What does NN leave when divided by any prime in the list?

Unfamiliar proofs

Negate it carefully, translate the assumption into algebra, then manipulate until you reach a contradiction.

Strategy for a new statement: (1) negate it carefully, (2) translate the assumption into algebra, (3) manipulate to a contradiction.

Typical contradictions: even equals odd; a fraction not in lowest terms; an integer between 0 and 1; a number divisible by 5 that equals 1.

If you are stuck, write down exactly what the contradiction would look like and work towards it.

  1. 1

    Negate the statement

    write exactly what "not true" means

  2. 2

    Translate into algebra

    for example a rational number is a/b in lowest terms

  3. 3

    Manipulate

    use only valid steps

  4. 4

    Reach a contradiction

    so the assumption was false and the statement is true

Strategy for an unfamiliar proof by contradiction.

Statement

Example 1:
is irrational
Example 2:
there are no integers m,nm,n with 15m+25n=115m+25n=1

Negation

Example 1:
is rational
Example 2:
there are integers m,nm,n with 15m+25n=115m+25n=1

Worked example

Prove that log⁡23\log_2 3 is irrational.

What is the negation of "there are no integers m,nm,n with 15m+25n=115m+25n=1"?

Try an exam question

Prove by contradiction that 3\sqrt3 is irrational.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

What further assumption must be made at the start of the proof?

1 mark, marked against the mark scheme

Revision notes