Disproof by counter-example
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 , , , 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 " 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
The statement
a universal claim: every prime is odd
- 2
Look for a case
a number that meets the condition (prime) but breaks the conclusion
- 3
Test 2
2 is prime and even
- 4
Conclude
one counter-example is enough: the statement is false
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 , is prime".
- 1
Values to all give primes, so small cases do not help.
- 2
Try : .
- 3
, which is not 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:
- , , (the only even prime), and negative numbers if allowed;
- values on a boundary of an inequality, such as or for ;
- surds that cancel, such as and , or equal values, such as ;
- larger values when small ones fail, such as for "if is prime then is prime".
Algebra helps: means , so every with is a counter-example to .
Which value is a counter-example to " for all real "?
Presenting a disproof
State a specific counter-example, show it meets the conditions, and show the conclusion fails.
A complete disproof has three parts:
- State a specific counter-example.
- Show that it satisfies the conditions of the statement.
- Show that the conclusion is false for it.
Always show the working, such as , rather than just writing the number. A disproof is short.
- 1
State the value
a specific counter-example
- 2
Check the conditions
it must satisfy them
- 3
Show the conclusion fails
with working
Worked example
Disprove: "if and are irrational then is irrational".
- 1
Choose .
- 2
Conditions: both and are irrational.
- 3
Conclusion: , which is rational.
Worked example
Disprove: "the sum of two primes is even".
- 1
Choose and .
- 2
Conditions: both are prime.
- 3
Conclusion: , which is odd.
To disprove "if is prime then is prime", which 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
Read the statement
decide whether it looks true or false
- 2
Looks false
search for a counter-example; one is enough to disprove it
- 3
Looks true
prove it by deduction or exhaustion
- 4
No counter-example found
this is evidence, not proof
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 is odd then is a multiple of 8.
- 1
Let for an integer .
- 2
Then .
- 3
is a product of consecutive integers, so it is even.
- 4
So for some integer .
A claim has been tested for 1000 cases with no counter-example. Is it proved?
Try an exam question
Disprove the statement: " is prime for every positive integer ".
[3 marks]
- [1]Choose the counter-example .
- [1].
- [1] is not prime, so the statement is false.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which value of is a counter-example to the claim?
1 mark, marked against the mark scheme
Which value of is a counter-example to the claim?
1 mark, marked against the mark scheme