Proof by contradiction

Proof by contradiction

Spec A1 · AQA A-Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • To prove SS by contradiction, assume the negation of SS and show this is impossible.
  • A correct negation is the key: "all" becomes "some ... does not".
  • 2\sqrt2 is irrational: assume pq\frac pq in lowest terms, then pp and qq are both even.
  • There are infinitely many primes: N=p1p2⋯pn+1N=p_1p_2\cdots p_n+1 has a prime factor not on the list.
  • State the assumption, each step with a reason, the contradiction and the conclusion.

The method

To prove a statement SS by contradiction, assume the opposite and show that this is impossible.

Write the conclusion explicitly: "this is a contradiction, so the assumption is false, hence ...".

The contradiction may be with the assumption itself or with something already known.

  1. 1

    Assume the negation

    Assume SS is false, that is, assume the negation of SS.

  2. 2

    Reason logically

    Use correct logical steps from that assumption.

  3. 3

    Reach a contradiction

    Something impossible, such as a number that is both odd and even.

  4. 4

    Conclude

    The assumption was wrong, so SS is true.

The four steps of a proof by contradiction

To prove by contradiction that "there is no largest even integer", what do you assume first?

Writing the negation

A correct negation is the key to a correct proof. Write the statement with "all" and "there exists", and negate each.

A rational number can be written as pq\frac{p}{q} with pp, qq integers, q≠0q\neq0. In lowest terms, pp and qq have no common factor greater than 11. Taking lowest terms is what produces the contradiction in irrationality proofs.

  1. 1

    Write the statement in full

    with “all” or “there exists”

  2. 2

    Swap the quantifier

    “all” becomes “there exists”, and the reverse

  3. 3

    Negate the property

    for example irrational becomes rational

  4. 4

    Assume the negation is true

    this is the start of the contradiction proof

Negating a statement correctly.

Statement

  • xx is irrational
  • There are no integers with property PP
  • There are finitely many primes
  • All xx satisfy PP

Negation

  • xx is rational
  • There exist integers with PP
  • There are infinitely many primes
  • Some xx does not satisfy PP

What is the negation of "all prime numbers are odd"?

√2 is irrational

Assume 2=pq\sqrt2=\frac pq in lowest terms. Squaring shows pp and qq are both even, contradicting lowest terms.

The same method proves 3\sqrt3 irrational: p2=3q2p^2=3q^2 gives 3∣p23\mid p^2, so 3∣p3\mid p (as 33 is prime), and then 3∣q3\mid q.

  1. 1

    Assume

    2=pq\sqrt2=\frac pq in lowest terms

  2. 2

    Square

    p2=2q2p^2=2q^2, so pp is even

  3. 3

    Substitute

    p=2kp=2k gives q2=2k2q^2=2k^2, so qq is even

  4. 4

    Contradict

    p and q share the factor 2

Why √2 cannot be rational

Worked example

Prove that 2\sqrt2 is irrational.

In the proof for 3\sqrt3, why does 3∣p23\mid p^2 imply 3∣p3\mid p?

Infinitely many primes

Assume finitely many primes, multiply them and add 1. The result has a prime factor not on the list.

Assume there are finitely many primes p1,…,pnp_1,\ldots,p_n, and let N=p1p2⋯pn+1N=p_1p_2\cdots p_n+1. Dividing NN by any pip_i leaves remainder 11, so no pip_i divides NN. But N>1N>1 is either prime or has a prime factor, which is not on the list.

NN need not itself be prime: 2×3×5×7×11×13+1=30031=59×5092\times3\times5\times7\times11\times13+1=30031=59\times509, with both factors new primes.

  1. 1

    Assume

    finitely many primes, p1,…,pnp_1,\ldots,p_n

  2. 2

    Build N

    N=p1p2⋯pn+1N=p_1p_2\cdots p_n+1

  3. 3

    Remainder 1

    no pip_i divides NN

  4. 4

    Contradict

    N has a prime factor not on the list

Euclid's proof

If the "list of all primes" is 2, 3, 5, what is N, and what does it show?

Unfamiliar proofs

Typical approaches use parity, a known irrational, or factorising. Always state the assumption, each step with a reason, the contradiction and the conclusion.

To show log⁡23\log_23 is irrational, assume log⁡23=pq\log_23=\frac pq, so 3q=2p3^q=2^p: an odd number equal to an even one.

To show 3+223+2\sqrt2 is irrational, assume it equals ab\frac ab, so 2=a−3b2b\sqrt2=\frac{a-3b}{2b}, rational: a contradiction.

To show a2−b2=1a^2-b^2=1 has no positive integer solutions, (a−b)(a+b)=1(a-b)(a+b)=1 forces a+b=a−b=1a+b=a-b=1, so b=0b=0.

  1. 1

    Assume log₂3 = p/q

    with p, q positive integers

  2. 2

    Rearrange

    3^q = 2^p

  3. 3

    Compare parity

    3^q is odd but 2^p is even

  4. 4

    Contradiction

    so log₂3 is irrational

A parity proof that log₂3 is irrational.

Parity

  • log⁡23=pq\log_23=\frac pq gives 3q=2p3^q=2^p
  • Odd equals even

Known irrational

  • 3+22=ab3+2\sqrt2=\frac ab
  • 2=a−3b2b\sqrt2=\frac{a-3b}{2b} is rational

Factorising

  • (a−b)(a+b)=1(a-b)(a+b)=1
  • Forces b=0b=0

Assume 3+22=ab3+2\sqrt2=\frac{a}{b} with integers aa, bb and b≠0b\neq0. Which statement leads to the contradiction?

Try an exam question

Prove by contradiction that there are no positive integers aa and bb such that a2−b2=1a^2-b^2=1.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which of these is the correct first line of the proof?

1 mark, marked against the mark scheme

Revision notes