Negation and Quantifiers

What you will 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 quantifiers "for all" and "there exists" (including a couple of those stacked together).

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. Another definition is: $\neg P$ is a statement such that in any given situation, precisely one of $P$ or $\neg P$ is true.

Negating basic statements

Negating everyday mathematical statements is just based on the idea of: $\neg P$ is true exactly when $P$ is false, and false exactly when $P$ is true.

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

Negating a negation!

This may or may not be obvious, but $\neg(\neg P)$ is simply $P$. Here are some examples:

• The negation of "$x \neq 5$" is "$x = 5$".
• The negation of "Jane is not in London" is "Jane is in London".
• The negation of "$n$ is odd" is "$n$ is even". Notice how naturally this flows!

Negating "and"

A statement of the form "$P$ and $Q$" is true when both $P$ and $Q$ are true. Therefore, its negation is: $P$ and $Q$ are not both true. In other words, at least one of them must be false: either $P$ is false, or $Q$ is false.

Formally, we write

Here are some examples:

• The negation of "$x>3$ and $x<10$" is "$x\leq 3$ or $x\geq 10$".
• The negation of "James is naughty and clever" is "James is not naughty or James is not clever".
• The negation of "$n$ is even and $n>5$" is "$n$ is odd or $n\leq 5$", assuming $n$ is an integer.

The same idea holds for more than two statements:

• The negation of "James likes football, swimming and tennis" is "James does not like football, or James does not like swimming, or James does not like tennis".
• Notice that a more succinct way of saying the same thing is: "There is one sport, or at least one sport, among football, swimming and tennis that James does not like". This is a precursor to how we negate quantified statements involving and, which we will discuss shortly!

Negating "or"

A statement of the form "$P$ or $Q$" is true when at least one of $P$ and $Q$ is true. Therefore, its negation is that $P$ and $Q$ are both not true.

Formally, we write

The very keen-eyed among you may notice that we can obtain $(2)$ from $(1)$ by reading $(1)$ in reverse and replacing $\neg P$ with $P$ and $\neg Q$ with $Q$.

Here are some examples:

• The negation of "$x>3$ or $x<0$" is "$x\leq 3$ and $x\geq 0$".
• The negation of "James is naughty or clever" is "James is not naughty and James is not clever".
• The negation of "$n$ is even or $n>5$" is "$n$ is odd and $n\leq 5$", assuming $n$ is an integer.

The same idea holds for more than two statements:

• The negation of "James likes football, swimming or tennis" is "James does not like football, and James does not like swimming, and James does not like tennis".
• Notice that a more succinct way of saying the same thing is: "James likes none of football, swimming and tennis". This is a precursor to how we negate quantified statements involving or, which we will discuss shortly!

Quantifiers

Interesting mathematical claims are often about whole collections of objects, and these two phrases are often used:

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

So "$\forall x \in \mathbb{R},\ x^2 \geq 0$" reads "for every real number $x$, $x^2$ is non-negative", and "$\exists n \in \mathbb{Z},\ n^2 = 9$" reads "There exists an integer $n$ for which $n$ squared is $9$".

Negating "for all" quantifiers

The quantifier for all is a general version of and, since for all requires all the involved statements to be true. Therefore, its negation is that at least one of the involved statements is false, or equivalently, that there exists one case for which the statement is false.

Here are some examples:

• The negation of "For all primes $p$, $p$ is odd" is "There exists a prime $p$ that is not odd".
• The negation of "Every multiple of 2 is a multiple of 4" is "There exists a multiple of 2 that is not a multiple of 4".
• The negation of "For every positive integer $n$, $\sum_{r=1}^n r = n(n+1)/2$" is "There exists a positive integer $m$ for which $\sum_{r=1}^m r \neq m(m+1)/2$".

Negating "there exists" quantifiers

The quantifier there exists is a general version of or, since there exists only requires at least one of the involved statements to be true. Therefore, its negation is that none of the involved statements is true, or equivalently, that for all of the statements involved, each statement is false.

Here are some examples:

• The negation of "There exists a prime $p$ that is even" is "For all primes $p$, $p$ is not even".
• The negation of "There exists a multiple of 2 that is not a multiple of 4" is "Every multiple of 2 is a multiple of 4".
• The negation of "There exists a positive integer $m$ for which $\sum_{r=1}^m r \neq m(m+1)/2$" is "For every positive integer $n$, $\sum_{r=1}^n r = n(n+1)/2$".

Negating "for all" and "there exists" quantifiers: algebraic rules

We can summarise these negation rules with one short, memorable phrase:

Swap the quantifier and negate the inside. That is,

and

Here are some examples.

• The negation of "For all primes $p$, $p$ is odd" is "There exists a prime $p$ such that $p$ is not odd".
• The negation of "$\forall n\in\mathbb{Z}^+,\ n^2\geq n$" is "$\exists n\in\mathbb{Z}^+$ such that $n^2<n$".
• $\neg\left(\exists x\in\mathbb{R},\ x^2=2\right) \equiv \forall x\in\mathbb{R},\ x^2\neq 2.$
• $\neg\left(\exists n\in\mathbb{Z},\ n \text{ is odd and } n \text{ is even }\right) \equiv \forall n\in\mathbb{Z}, n \text{ is even or } n \text{ is odd}.$

Negating nested quantifiers

Nested quantifiers are statements where one quantifier sits inside another, such as "for all ... there exists ..." or "there exists ... such that for all ...". The key rule is the same as before: swap each quantifier and negate the inside, working from the outermost quantifier inwards, one layer at a time.

For example,

Similarly,

Now I give a couple of actual concrete mathematical examples, these are definitions that naturally use nested statements involving quantifiers.

Example 1: Local maximum of a function $f(x)$

We define $f$ to have a local maximum at $x=a$ if

Intuitively, this is saying $x=a$ is a local maximum if you can find a small interval around $a$ for which $f(x)$ of all the $x$ in that interval is not greater than $f(a)$.

Now let us examine what it means for $x=a$ not to be a local maximum. This is the negation of the statement above:

So the negation is

Intuitively, this is saying that no matter how small a neighbourhood we choose around $a$, there is always some $x$ in that neighbourhood with $f(x)>f(a)$, so $x=a$ is not a local maximum.

Example 2: Continuity of a function $f(x)$ at a point

We define $f$ to be continuous at $x=a$ if

This is a difficult definition to understand, and it is usually first taught at undergraduate level. Intuitively, the idea of $f$ is continuous at $x=a$ is that $f$ passes $x=a$ without jumps or sudden breaks. If $x$ is sufficiently close to $a$, then $f(x)$ is also very close to $f(a)$. I will leave the intuition at this level, as this part is optional! However, we can nonetheless find its negation.

Now let us examine what it means for $f$ not to be continuous at $x=a$. This is the negation of the statement above:

So the negation is

Intuitively, this says that we can find a gap $\epsilon > 0$ for which, no matter how small a non-zero interval we choose around $x=a$, we can always find a $x^*$ inside that interval, for which $|f(x^*) - f(a)| \geq \epsilon$. In this case, $f$ is not continuous at $a$, as the $x$ near it, not all $f(x)$ converge to $f(a)$. What I gave here again is a hand wavy explanation to aid intuition, not a precise definition or statement, for that is where we turn to the formal negation!

Summary

• $\neg P$ is true exactly when $P$ is false.
• $\neg(\neg P)$ is $P$.
• "$\neg(P \text{ and } Q)$" is "$\neg P \text{ or } \neg Q$".
• "$\neg(P \text{ or } Q)$" is "$\neg P \text{ and } \neg Q$".
• Rule for negating quantifiers: swap the quantifier and negate the inside.
• When negating statements with nested quantifiers, apply swap the quantifier and negate the inside recursively, starting from the outermost quantifier.