Negation and Counter-Examples

What you'll get from this section. You'll learn how to write the opposite of a statement correctly: simple statements, statements joined by "and" or "or", and statements involving "for all" and "there exists" (including a couple of those stacked together). Then you'll see how negation hands you the single most efficient tool for disproving a sweeping claim — the counter-example.

We set the implication arrow aside completely for this section; it returns in Section 4.

What negation is

The negation of a statement $P$ is the statement "not $P$", written $\neg P$. It is true exactly when $P$ is false, and false exactly when $P$ is true. Negating twice gets you back to where you started: $\neg(\neg P)$ is just $P$.

Negating everyday mathematical statements is mostly common sense, with one notorious trap:

• "$x$ is even" negates to "$x$ is odd" (for an integer).
• "$x = 5$" negates to "$x \neq 5$".
• "$x > 3$" negates to "$x \leq 3$" — not "$x < 3$".

That last one catches almost everyone. The opposite of "greater than $3$" has to include $3$ itself, because $3$ is not greater than $3$. So the negation of $>$ is $\leq$, and the negation of $\geq$ is $<$.

Negating "and" and "or"

When a statement is built from two parts, negation flips the joining word:

These are De Morgan's laws. The intuition is plain. For the first: if it's not true that both $P$ and $Q$ hold, then at least one of them must fail. For the second: if neither happens, then $P$ fails and $Q$ fails.

For instance, the negation of "$n$ is positive and even" is "$n$ is not positive or $n$ is not even" — i.e. $n$ is either non-positive or odd (or both). (You may also meet "and" and "or" written with the symbols $\land$ and $\lor$.)

Quantifiers: "for all" and "there exists"

Most interesting mathematical claims are about whole collections of objects, and two little phrases do that work:

• "for all", written $\forall$: $\forall x,\ P(x)$ means every $x$ has the property $P$.
• "there exists", written $\exists$: $\exists x,\ P(x)$ means at least one $x$ has the property $P$.

So "$\forall x \in \mathbb{R},\ x^2 \geq 0$" reads "every real number has a non-negative square", and "$\exists n \in \mathbb{Z},\ n^2 = 9$" reads "some integer has square $9$".

Negating quantifiers

Here negation does something clean and memorable: it swaps the quantifier and negates the inside.

Read them aloud and they're obvious. If it's not true that everything has property $P$, then something must fail it. If nothing has property $P$, then everything fails it. (Notice the family resemblance to De Morgan: $\forall$ behaves like a long string of "and"s, $\exists$ like a long string of "or"s.)

An example. Take "every prime is odd", written "$\forall$ prime $p,\ p$ is odd". Its negation is

that is, "some prime is even". (That negation happens to be true — hold that thought for the last part of this section.)

Everyday version: the negation of "all swans are white" is not "all swans are non-white" — it's "there exists a swan that is not white". A single black swan does it.

Nested quantifiers

Statements often stack quantifiers. To negate them, apply the same rule repeatedly: keep the quantifiers in the same order, flip each one's type, and negate the statement they govern.

For a concrete case, consider

"for every real number there is a larger one" (true). Flipping each quantifier and negating the inside gives

"there is a real number that every other is less than or equal to" — a largest real number. That's false, which fits: the original was true, so its negation should be false.

In words it's just as natural. The negation of "everyone has someone they admire" is "there is someone who admires no one" — $\exists$ a person who, $\forall$ people, does not admire them.

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.

Next: Section 4 — The Contrapositive.