Disproof by counter-example

Disproof by counter-example

Spec A1 · AQA A-Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A counter-example meets the conditions but breaks the conclusion, and one is enough to disprove a statement.
  • No number of confirming examples proves a general statement.
  • Try 00, 11, 22, negatives, boundary values, equal values and fractions first.
  • A disproof states the value, shows the conditions hold, and shows the conclusion fails.
  • If no counter-example is found, that is evidence, not proof.

What a counter-example is

A counter-example is a single case that satisfies a statement's conditions but makes its conclusion false.

A counter-example disproves a universal statement of the form "for all nn" or "if ... then ...".

  • One counter-example is enough to disprove a statement.
  • No number of confirming examples proves a general statement.
  • A statement that has been proved true can never have a counter-example.
  1. 1

    The statement

    a universal claim: every prime is odd

  2. 2

    Look for a case

    a number that meets the condition (prime) but breaks the conclusion

  3. 3

    Test 2

    2 is prime and even

  4. 4

    Conclude

    one counter-example is enough: the statement is false

Disproving "all prime numbers are odd"

Disproves

  • One counter-example
  • Meets the conditions, breaks the conclusion

Never proves

  • Any number of confirming examples
  • A proved statement has no counter-example

Worked example

Disprove: "for every positive integer nn, n2+n+41n^2+n+41 is prime".

How many counter-examples are needed to disprove a statement?

Finding a counter-example

Test small and special cases first, then boundary values and larger numbers.

Test these first:

  • n=0n=0, n=1n=1, n=2n=2 (the only even prime), and negative numbers if allowed;
  • values on a boundary of an inequality, such as x=0x=0 or x=1x=1 for x2>xx^2>x;
  • surds that cancel, such as 2\sqrt2 and −2-\sqrt2, or equal values, such as 2×2=2\sqrt2\times\sqrt2=2;
  • larger values when small ones fail, such as n=11n=11 for "if nn is prime then 2n−12^n-1 is prime".

Algebra helps: x2≤xx^2\le x means x(x−1)≤0x(x-1)\le0, so every xx with 0≤x≤10\le x\le1 is a counter-example to x2>xx^2>x.

−1−0.50.511.52−11234xy(0, 0)(1, 1)y = x²y = x
The curve y=x2y=x^2 is not above y=xy=x for 0≤x≤10\le x\le1.

Which value is a counter-example to "x2>xx^2>x for all real xx"?

Presenting a disproof

State a specific counter-example, show it meets the conditions, and show the conclusion fails.

A complete disproof has three parts:

  1. State a specific counter-example.
  2. Show that it satisfies the conditions of the statement.
  3. Show that the conclusion is false for it.

Always show the working, such as 211−1=2047=23×892^{11}-1=2047=23\times89, rather than just writing the number. A disproof is short.

  1. 1

    State the value

    a specific counter-example

  2. 2

    Check the conditions

    it must satisfy them

  3. 3

    Show the conclusion fails

    with working

A complete disproof

Worked example

Disprove: "if xx and yy are irrational then xyxy is irrational".

Worked example

Disprove: "the sum of two primes is even".

To disprove "if nn is prime then 2n−12^n-1 is prime", which nn works?

Proof versus disproof

If a statement looks false, search for a counter-example; if it looks true, prove it.

If you cannot find a counter-example, that does not show the statement is true: you need a proof.

Strong claims such as "for all" are the easiest to disprove. A claim that something exists needs one example to prove it.

Testing many cases and finding no counter-example is evidence, not proof.

  1. 1

    Read the statement

    decide whether it looks true or false

  2. 2

    Looks false

    search for a counter-example; one is enough to disprove it

  3. 3

    Looks true

    prove it by deduction or exhaustion

  4. 4

    No counter-example found

    this is evidence, not proof

Disprove or prove?

Looks false

  • Search for a counter-example

Looks true

  • Prove it by deduction or exhaustion

Many tests, none fail

  • Evidence, not proof

Worked example

Prove: if nn is odd then n2−1n^2-1 is a multiple of 8.

A claim has been tested for 1000 cases with no counter-example. Is it proved?

Try an exam question

Disprove the statement: "n2+n+11n^2+n+11 is prime for every positive integer nn".

[3 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which value of nn is a counter-example to the claim?

1 mark, marked against the mark scheme

Revision notes