Most claims in mathematics are "for all" claims: for every integer, for every triangle, for every graph. You learned that the negation of "for all" is "there exists one that fails." That one fact gives the fastest tool for showing a claim is false.
Key idea
To disprove "for all $x$, if $P(x)$ then $Q(x)$," give one counterexample: a value of $x$ for which $P(x)$ is true and $Q(x)$ is false. One counterexample is a complete disproof. On the other hand, no number of examples that agree can prove a "for all" claim.
Why it works
The claim is $\forall x\, (P(x) \to Q(x))$. Its negation is $\exists x\, (P(x) \wedge \neg Q(x))$: some $x$ satisfies the hypothesis and breaks the conclusion. Exhibiting such an $x$ proves the negation, so the claim is false. Examples that agree show nothing, because the claim might still fail at a value you have not checked, possibly a very large one.
Worked examples
Worked example: A formula that looks prime-producing
Claim: for every positive integer $n$, $n^{2} + n + 41$ is prime. Disprove it.
- The first values are $43, 47, 53, 61, 71, \ldots$, all prime, and in fact every value for $n = 1$ to $39$ is prime. That still proves nothing.
- Look for a value where the formula factors. At $n = 40$: $40^{2} + 40 + 41 = 40 \cdot 41 + 41 = 41 \cdot 41$.
- $1681 = 41^{2}$ is not prime, so $n = 40$ is a counterexample (and the smallest one).
Answer: $n = 40$, since $40^{2} + 40 + 41 = 41^{2}$
Worked example: A counterexample must satisfy the hypothesis
Claim: if $x > 0$, then $x^{3} > x$. Which of $x = -2$ and $x = \frac{1}{2}$ is a counterexample?
- $x = -2$: the conclusion fails ($-8$ is not greater than $-2$), but the hypothesis $x > 0$ fails too. The claim says nothing about negative $x$, so this is not a counterexample.
- $x = \frac{1}{2}$: the hypothesis holds ($\frac{1}{2} > 0$), and $x^{3} = \frac{1}{8}$, which is not greater than $\frac{1}{2}$. The conclusion fails.
- So $x = \frac{1}{2}$ is a counterexample.
Answer: $x = \frac{1}{2}$
Worked example: The smallest counterexample
Claim: for every positive integer $n$, $2^{n} + 1$ is prime. Find the smallest counterexample.
- Test in order. $n = 1$: $3$, prime. $n = 2$: $5$, prime.
- $n = 3$: $2^{3} + 1 = 9 = 3 \cdot 3$, not prime.
- So the smallest counterexample is $n = 3$.
Answer: $n = 3$
Common mistake
Two opposite slips. One is offering agreeing examples as if they proved a claim: checking $n = 1, 2, 3$ cannot settle a statement about every $n$. The other is giving a "counterexample" that does not satisfy the hypothesis, like $x = -2$ above. Check: a counterexample must make the "if" part true and the "then" part false. Write both checks down.
Famous claims have failed late. Fermat guessed that every number $2^{2^{n}} + 1$ is prime; the first five are, but Euler showed that $2^{32} + 1 = 641 \cdot 6{,}700{,}417$.