Counter-examples

A claim of the form "$\forall x,\ P(x)$" — every object has some property — is exactly the kind we just learned to negate, and its negation is "$\exists x,\ \neg P(x)$": there is one object that fails. That single object is a counter-example, and producing one is all it takes to prove the universal claim false.

This gives a powerful asymmetry. To prove a "for all" claim you need a general argument covering every case; but to disprove it you need just one well-chosen example.

• "Every prime is odd." Counter-example: $2$, which is prime and even. One number settles it.
• "$n^2 > n$ for every positive integer $n$." Counter-example: $n = 1$, since $1^2 = 1$, which is not greater than $1$.
• "$n^2 + n + 41$ is prime for every whole number $n$." This is prime for $n = 0, 1, 2, \dots, 39$ — thirty-nine straight successes — and yet it is false. At $n = 40$,

which is not prime. Thirty-nine confirming cases prove nothing; one counter-example demolishes the claim.

That third example carries the real lesson: piling up examples that agree with a universal claim never establishes it, but a single example that disagrees refutes it outright.

Common mistakes

1. Negating $>$ as $<$. The negation of "$x > 3$" is "$x \leq 3$", not "$x < 3$" — the boundary value belongs to the negation. Likewise $\geq$ negates to $<$.

2. Forgetting to swap the quantifier. The negation of "$\forall x,\ P(x)$" is "$\exists x,\ \neg P(x)$" — you must change $\forall$ to $\exists$ and negate the inside, not just one of the two.

3. Reordering nested quantifiers. When negating, keep the quantifiers in their original order; only their types flip. $\forall x\, \exists y$ negates to $\exists x\, \forall y$, with $x$ still first.

4. Trying to confirm a "for all" claim with examples. Examples can only ever disprove a universal statement (via a counter-example); they can never prove one.

Summary

• $\neg P$ is true exactly when $P$ is false; $\neg(\neg P)$ is $P$.
• The negation of $>$ is $\leq$ (and of $\geq$ is $<$).
• De Morgan: "not (P and Q)" is "(not P) or (not Q)"; "not (P or Q)" is "(not P) and (not Q)".
• Negating a quantifier swaps $\forall \leftrightarrow \exists$ and negates the inside; for nested quantifiers, do this to each in turn, keeping their order.
• A single counter-example disproves a "for all" claim — and no number of agreeing examples can prove one.