Counterexample
Someone claims a rule works for every number. What does it take to prove them wrong, and what can never do it?
Where you are 14 in Proof techniques
When you reach for it
A claim that something holds for every member of a collection is a universal statement, a “for all”. Proving one takes an argument that covers every member at once. Refuting one takes much less: a single member for which it fails. That member is a counterexample.
Reach for one whenever a claim says “every”, “all”, “always” or “never”, or hides that word inside an “if ... then” (“if a number is prime, it is odd” means every prime is odd). It is the first test to run on a guess of your own, before spending an hour trying to prove it, and the fastest answer to someone else’s.
The procedure
What counts. For a claim \forall x \in D,\ P(x), a counterexample is a member a of the domain D with P(a) false. Most claims have the shape “for every x, if H(x) then C(x)”, and then a counterexample is a member that makes the hypothesis H true and the conclusion C false. A member that makes H false cannot break the claim, because an if-then with a false “if” part is true (the truth table for the conditional).
Why one is enough. Negating the claim gives
and a “there exists” is proved by showing one object that does the job. The counterexample is that object.
Where to look. A claim is usually a generalization from the cases its author had in mind, so its failures hide in the cases they did not picture: 0, 1, negative numbers, fractions between 0 and 1, two values that are equal, the smallest allowed case, a square counted as a rectangle. A second place to look is the claim’s structure: factor it, and ask which inputs would make every term share a factor, or make two terms cancel. A third is a failed proof. Try to prove the claim, and note the step that needs something extra, such as “x is positive”. Inputs without that extra property are where to search.
Checking it really fails. Show both halves, exactly. The candidate must lie in the domain and meet every hypothesis, and the conclusion must be shown false by exact arithmetic that the reader can repeat: a factorization written out, two numbers compared, not “it looks composite” or a rounded calculator display.
The examples show each of these at work, and the last one shows what a counterexample cannot do.
Worked examples
A candidate that counts, and one that does not
Claim: for all real numbers a and b, if a > b, then a^2 > b^2. Decide whether the pairs (a, b) = (5, 3), (-3, 2) and (1, -2) are counterexamples.
SolutionA counterexample must make a > b true and a^2 > b^2 false.
(5, 3): 5 > 3, and 25 > 9. The claim holds here, so this is not a counterexample. Every positive pair behaves this way, which is why the claim looks safe.
(-3, 2): -3 > 2 is false, so the hypothesis fails. The claim makes no promise about this pair, and it cannot break it. Not a counterexample.
(1, -2): 1 > -2 is true, and a^2 = 1, b^2 = 4, so 1 > 4 is false. Hypothesis true, conclusion false: this is a counterexample, and the claim is false.
The hunt went to negative numbers because the obvious proof, multiplying a > b by a and by b, needs both numbers positive. The pair (2, -2) breaks it too, since 4 > 4 is false.
Five successes, then a failure shown exactly
Claim: for every prime p, if you multiply together all the primes from 2 up to p and add 1, the result is prime.
SolutionThe only hypothesis is that p is prime, so every prime is a candidate. Try them in order.
| p | product of the primes up to p, plus 1 | prime? |
|---|---|---|
| 2 | 2 + 1 = 3 | yes |
| 3 | 6 + 1 = 7 | yes |
| 5 | 30 + 1 = 31 | yes |
| 7 | 210 + 1 = 211 | yes |
| 11 | 2310 + 1 = 2311 | yes |
Five successes prove nothing. The next prime is p = 13, which gives
This number is built to leave remainder 1 when divided by each of 2, 3, 5, 7, 11 and 13, so none of the small primes divides it, and it looks prime. It is not. To show that it really fails, write out a factorization:
and check the multiplication: 59 \times 509 = 59 \times 500 + 59 \times 9, which is 29500 + 531 = 30031. So 13 is prime and 30031 is not. The claim is false. What survives is weaker: every prime factor of 30031 is bigger than 13, and that weaker fact is the one Euclid used to show that there are infinitely many primes.
Hunting with the structure of the claim
Claim: for every non-negative integer n, the number 2n^2 + 29 is prime.
SolutionThe first values, for n = 0 to 10, are 29, 31, 37, 47, 61, 79, 101, 127, 157, 191, 229, all prime. Trying n one at a time, you would need 30 tries: every n from 0 to 28 gives a prime.
Look at the formula instead. If n is a multiple of 29, both terms are multiples of 29, so their total is too. The simplest choice is n = 29:
That number has the factor 29 and is larger than 29, so it is not prime, and the claim is false. The structure found in one step what a search finds only on its thirtieth try. The same move works on many claims of this shape: if a polynomial has whole-number coefficients and a constant term c > 1, then putting n = c makes every term a multiple of c, and the value is not prime as long as it is bigger than c.
One pair of shapes
Claim: any two rectangles with the same perimeter have the same area.
SolutionA counterexample is two rectangles with equal perimeters and unequal areas. Keep the perimeter at 16, so the length and width add to 8, and change the shape.
A 6 by 2 rectangle has perimeter 2(6 + 2) = 16 and area 6 \times 2 = 12. A 5 by 3 rectangle has perimeter 2(5 + 3) = 16 and area 5 \times 3 = 15. Same perimeter, areas 12 and 15: the claim is false. The long thin rectangle encloses less, and stretching it further, to 7 by 1, would bring the area down to 7.
A counterexample in logic
Claim: for all statements p, q and r, the statements (p \land q) \to r and (p \to r) \land (q \to r) are logically equivalent. It looks like “distributing” the arrow over the “and”.
SolutionHere the “members” are the rows of a truth table, and a counterexample is one row where the two statements have different truth values. Write A for {(p \land q) \to r} and B for {(p \to r) \land (q \to r)}.
An “and” is false as soon as one part is false, and an arrow is false only when its left side is true and its right side false. So take p true and r false: then p \to r is false, and B is false. To keep A true, its left side p \land q must be false, and with p true that means q false. On that row q \to r is true, but one false part is enough to make B false.
| p | q | r | A | B |
|---|---|---|---|---|
| T | F | F | T | F |
One row where they differ, so they are not equivalent. (The row with p false, q true and r false works as well.) In words: “if both hold, then r” promises less than “if either holds, then r”. The same idea tests an argument form, where a counterexample is a row with every premise true and the conclusion false, as in affirming the consequent.
A pair of numbers, and what the counterexample does not show
Claim: for all positive integers a and b, if a divides b^2, then a divides b.
SolutionA counterexample is a pair. If a is prime the claim holds (a prime that divides b \times b divides one of the factors, a separate theorem), so look at an a with a repeated factor. Take a = 4 and b = 2: b^2 = 4, and 4 divides 4, so the hypothesis holds. But 4 does not divide 2, since \displaystyle 2 \div 4 = \frac{1}{2}. The claim is false. The pair a = 9, b = 3 works the same way.
The counterexample refutes the claim as written, for all a. It does not show that the claim fails for most pairs, and it says nothing about the repaired claim “if a prime a divides b^2, then a divides b”, which is true and needs a proof of its own.
Where a counterexample cannot help
Claim A: there is a positive integer n for which 991n^2 + 1 is a perfect square. A computer checks every n from 1 to 1{,}000{,}000 and finds none. Is Claim A refuted?
SolutionNo. Claim A is an existence claim, a “there exists”. One failing n refutes a “for all”, but an existence claim is compatible with any number of failures: it needs only one success somewhere. To refute Claim A you would have to prove its negation, “for every positive integer n, 991n^2 + 1 is not a square”, and that is a claim about infinitely many numbers, which a million checks cannot settle.
In fact Claim A is true. The smallest n that works has 29 digits, and it makes 991n^2 + 1 equal to m^2, where m is a 30-digit number:
That is far beyond any search by trial. So the million failures were not a counterexample to anything, and the negation, which survived a million checks without a counterexample, was false all along.
Boundaries
It must come from the domain and meet the hypothesis. The pair (1, -2) refutes the claim of Example 1 over the real numbers. Over the positive reals the same claim is true, and no counterexample exists.
It refutes only “for all”. Claimed identities, equivalences and valid argument forms are “for all” statements in disguise, so a counterexample refutes them too (disproving an identity). A “there exists” claim is refuted only by proving that every member fails (Example 7).
Not finding one proves nothing, unless the domain is finite. On an infinite domain, a search that turns up no counterexample is evidence at most (a pattern is not a proof). On a finite domain, checking every member and finding no failure is a complete proof.
It kills the claim as stated, and nothing more. It does not say how often the claim fails, and a narrower claim may be true (Example 6).
Where this goes next
A claim that nobody has yet proved or refuted is a conjecture, and the working life of a conjecture is a hunt for counterexamples alongside an attempt at a proof. In geometry, where a claim is often read off a drawing, the same move appears as conjectures and counterexamples. When the hunt keeps failing, the next step is a proof: direct proof, proof by contradiction or induction. And every theorem has a converse whose truth is a separate question, which a counterexample is often the quickest way to settle.
Exercises
Does it count?
- Claim: for every real x, x^3 > x. Is x = 2 a counterexample? Is \displaystyle x = \frac{1}{2}?
- Claim: for every positive integer n, if n is a multiple of 4, then n is a multiple of 8. Which of 6, 12 and 16 are counterexamples?
- Claim: for all nonzero real numbers a and b, if a < b, then \displaystyle \frac{1}{a} > \frac{1}{b}. Is a = -1, b = 2 a counterexample?
- Claim: for all integers a and b, if a is odd or b is odd, then a + b is odd. A student offers a = 2, b = 4 as a counterexample. Is it one? If not, give one.
Find a counterexample
- For every positive integer n, n^2 + n + 1 is prime.
- For every positive integer n, 2^n + 1 is prime.
- For every real x, \lvert x + 3 \rvert = \lvert x \rvert + 3.
- For every positive integer n, if n^2 is a multiple of 8, then n is a multiple of 8.
- For all positive integers a, b and c, if a divides bc, then a divides b or a divides c.
- For every non-negative integer n, 2n^2 + 11 is prime. Use the structure of the expression, not a search.
- Any two rectangles with the same area have the same perimeter.
Numbers and logic
- The product of two irrational numbers is irrational.
- The sum of two irrational numbers is irrational.
- For all statements p, q and r, (p \lor q) \to r is logically equivalent to (p \to r) \lor (q \to r).
- For all statements p, q and r, p \land (q \lor r) is logically equivalent to (p \land q) \lor r.
What it can and cannot do
- Claim: there is an integer n with n^2 = 2n + 3. A student tries n = 0, 1 and 2, finds that none works, and calls the claim refuted. Is it? Decide whether the claim is true.
- Claim: some real number x satisfies x^2 + 6x + 10 = 0. A student says “x = 1 is a counterexample, since 1 + 6 + 10 = 17.” Explain what is wrong, and decide whether the claim is true.
- Exercise 5 has a counterexample. Does that show that n^2 + n + 1 is never prime? Explain.
Reasoning
- Explain, using the negation of \forall x \in D,\ P(x), why one counterexample is enough to show the statement is false.
- Show that the claim “for every real x, x^2 - 2x + 2 > 0” has no counterexample. Why does this need an argument rather than a search?
- Explain why a member of the domain that makes the hypothesis of an if-then claim false can never be a counterexample to it.
Answers
- x = 2 is not: 8 > 2 holds. \displaystyle x = \frac{1}{2} is: \displaystyle \frac{1}{8} > \frac{1}{2} is false.
- Only 12. It is a multiple of 4 but not of 8. 6 is not a multiple of 4, so it misses the hypothesis; 16 is a multiple of both, so it passes.
- Yes. -1 < 2 is true, but \displaystyle \frac{1}{a} = -1 and \displaystyle \frac{1}{b} = \frac{1}{2}, and \displaystyle -1 > \frac{1}{2} is false.
- No: 2 and 4 are both even, so the hypothesis fails. A counterexample is a = 1, b = 3: both are odd, so “a is odd or b is odd” is true (the “or” allows both), but 1 + 3 = 4 is even.
- n = 4 gives 16 + 4 + 1 = 21 = 3 \times 7. (n = 1, 2 and 3 give the primes 3, 7 and 13.)
- n = 3 gives 2^3 + 1 = 9 = 3 \times 3.
- x = -1: \lvert -1 + 3 \rvert = 2, but \lvert -1 \rvert + 3 = 4. Any negative x works.
- n = 4: n^2 = 16 = 8 \times 2, but 4 is not a multiple of 8.
- a = 6, b = 2, c = 3: 6 divides bc = 6, but 6 divides neither 2 nor 3.
- n = 11. Both terms are then multiples of 11: 2 \times 11^2 + 11 = 11 \times (2 \times 11 + 1), which is 11 \times 23 = 253 and not prime. (Every n from 0 to 10 gives a prime, so a search would take twelve tries.)
- A 1 by 12 rectangle and a 3 by 4 rectangle both have area 12, but their perimeters are 26 and 14.
- \displaystyle \sqrt{2} \times \sqrt{2} = 2. Both factors are irrational (\displaystyle \sqrt{2} is irrational) and the product is rational.
- \displaystyle \sqrt{2} + (-\sqrt{2}) = 0, which is rational. \displaystyle -\sqrt{2} is irrational: if it were a fraction r, then \displaystyle \sqrt{2} = -r would be a fraction too.
- p true, q false, r false. Then p \lor q is true, so (p \lor q) \to r is false; but q \to r is true, so {(p \to r) \lor (q \to r)} is true.
- p false, r true (either q). Then p \land (q \lor r) is false, but (p \land q) \lor r is true.
- Not refuted: failures cannot refute a “there exists” claim. It is true, since n = 3 gives 9 = 9 (and n = -1 gives 1 = 1).
- A counterexample refutes a “for all” claim; this is a “there exists” claim, and one failing x says nothing about it. The claim is false, but that needs a proof about every x: x^2 + 6x + 10 = (x + 3)^2 + 1, and (x + 3)^2 \ge 0, so the value is at least 1 and never 0.
- No. It shows only that not every n gives a prime. It says nothing about the other values, and n = 1, 2 and 3 do give primes.
- The negation of \forall x \in D,\ P(x) is \exists x \in D,\ \neg P(x). A counterexample is a member a with P(a) false, which proves that “there exists” statement, so the original is false.
- x^2 - 2x + 2 = (x - 1)^2 + 1, and (x - 1)^2 \ge 0, so the value is at least 1 for every real x. A search checks only finitely many of the infinitely many real numbers, so it could never rule out a failure somewhere else.
- A counterexample must make the claim false for that member, and an if-then is false only when its “if” part is true and its “then” part false. With the “if” part false, the if-then is true for that member, so the member does not break the claim.