$Project Greater Ed Logo$

Quantifier Alternation and Negation

Discrete Mathematics Quantifiers Quantifier Alternation and Negation

Multiple Quantifiers and Rearranging Them

We’ve already see examples of statements that have multiple quantifiers, such as

“$\forall x \in \mathbb{R}, \exists y\in \mathbb{N}, $ such that $x<y$.”

Naturally, we aren’t limited to just zero, one, or two quantifiers per statement. A statement can have dozens of quantifiers! In fact, there are some mathematicians that study statements with infinitely many quantifiers! We will only deal with statements that have finitely many quantifiers and work to simplify them a bit.

Reducing Repeating Quantifiers

For statements where you see the same quantifiers repeated one after another, like the universal quantifiers in the statement

“For every real number $x$ and every real number $y$, there is a real number $z$ such that $x\leq z\leq y$,”

which, written with quantifiers, reads as

“$\forall x\in \mathbb{R}, \forall y\in \mathbb{R}, \exists z\in \mathbb{R}$ such that $x\leq z\leq y$,”

One can collapse the repeated quantifiers down to exactly one of that type by “bunching together” everything that has that same quantifier. In the statement above, where we have two “for all’s” in a row, we can combine them into just one single “for all.” Viz:

“For all real numbers $x$ and $y$, there exists a real number $z$ such that $x\leq z\leq y$”

which has symbolic representation

“$\forall x,y\in\mathbb{R}, \exists z\in \mathbb{R}$ such that $x\leq z\leq y$.”

Note that we collapsed the two “for all’s” down to a single “for all.” This can always be done no matter how many of the same quantifier you have “in a row.” This includes repeated “there exists” quantifiers.”

Key Idea

Every statement involving quantifiers can be written so that quantifiers alternate and so that the same quantifier is not listed repeatedly “in a row.”

That is, statements that, in form, look something like “$\forall a\ \forall b\ \exists c\ \exists d\ \exists e\ \forall f\ \forall g\ \exists h$” can be contracted down to read as “$\forall a,b,\ \exists c,d,e\ \forall f,g\ \exists h$” so that the quantifiers alternate and there are none repeated “in a row.”

CAVEAT: You cannot arbitrarily swap the order of DIFFERENT quantifiers, nor can you group the same type of quantifiers if they DO NOT occur “in a row.” For example, the statement

$\forall x\in \mathbb{R}, \exists y\in \mathbb{R}, \forall z\in \mathbb{R}, x\leq y\leq z$

cannot be rearranged or grouped so that the two “for all’s” occur together (“in a row”); i.e. the above is NOT the same statement as

$\forall x \in \mathbb{R}, \forall z\in \mathbb{R}, \exists y\in \mathbb{R}$ such that $x\leq y\leq z$.

Changing the order of quantifiers may change the meaning of the statement. See below.

Swapping Quantifiers

Take a look at the following two statements that only differ in the order their quantifiers appear:

“$\forall n\in \mathbb{N}, \exists m\in \mathbb{N}$ such that $n\vert m$.”
“$\exists m\in \mathbb{N}$ such that $\forall n\in \mathbb{N}$, $n\vert m$.”

Try to understand what each one is saying, and determine if the SAME EXACT IDEA is being communicated across both statements.

The first statement, in English, says that “For every natural number $n$ there is a (single) natural number $m$ that $n$ divides.” Put another way, “For any (natural) number one chooses, I can always find another number that it divides.”

The second statement, in English, says “There is a natural number $m$ such that for any (other) natural number $n$, $n$ divides $m$.” Put another way, “There is a single number that I can choose that every other natural number divides.”

With some thought, one can see that the two statements are not saying the same thing. To help with this, note that the first statement is true and the second one is false… AND ALL WE DID WAS CHANGE THE ORDER OF THE QUANTIFIERS!

Important Observation

Changing the order of quantifiers in a statement might yield an entirely different statement; i.e. a statement with a different meaning.

IMPORTANT NOTE: Changing the order of quantifiers in a statement does not necessarily change the meaning of the statement. That is, it can change the meaning; it just doesn’t have to. See if you can come up with an example for this!

Negating Quantified Statements

Negating Universal Statements

Recall that the negation of a statement $P$ is the statement with the opposite truth value of $P$.

What would be the negation of the statement “All cats hate water;” i.e. what statement could you make that has the opposite truth value?

The opposite statement would thus be “There is (or exists) at least one cat that does NOT hate water.”

The above example indicates how one can negate universally quantified statements.

Negating Universally Quantified Statements

Let $P(x)$ be a predicate and let $D$ be the domain of $x$. The negation of the statement “$\forall x\in D, P(x)$” is the statement “$\exists x\in D$ such that $\neg P(x)$.”

Symbolically: $\neg(\forall x\in D, P(x)) \equiv \exists x\in D\ \text{such that}\ \neg P(x)$.

In other words, when you claim the universal statement “$\forall x\in D, P(x)$” as true, you are asserting that $P(x)$ is true FOR EVERY SINGLE $x\in D$. Thus, the negation of such a statement is “$\exists x\in D$ such that $\neg P(x)$” which asserts that there is (at least) one value of $x$ for which the statement $P(x)$ is FALSE; i.e. there is at least one counterexample.

Solution: $\exists x\in \mathbb{N}$ such that $x\not>0$.

The original statement essentially says “every natural number is greater than zero.” So to negate this (or find the opposite statement), we note that the original statement is false if “there exists (at least) one natural number that is NOT less than 0.” That right there is your negation!

Negating Existential Statements

What would the negation of the statement “There is a cat that eats fish” be; i.e. what is the statement with the opposite truth value?

In this case, the negation of the above statement could be written as “No cat eats fish.” Put another way, “All cats DO NOT eat fish.”

Similarly, what is the negation of the statement “There are people who listen to classical music”? In this case, the negation could be written as “every person on earth does not listen to classical music.”

Both of the above examples indicate how one negates existential statements.

Negating Existential Statements

Let $P(x)$ be a predicate and let $D$ be the domain of $x$. The negation of the sentence “$\exists x\in D$ such that $P(x)$” is “$\forall x\in D, \neg P(x)$”

Symbolically: $\neg(\exists x\in D$ such that $P(x))\equiv \forall x\in D, \neg P(x)$

In other words, when you claim the original existential statement “$\exists x\in D$ such that $P(x)$” as true, you are asserting that there is at least one $x\in D$ where $P(x)$ is true. So, negating such a statement means that there is not a single $x\in D$ where $P(x)$ is true — alternatively for every $x\in D$ the statement $P(x)$ is FALSE!

Solution: “$\forall n\in \mathbb{N}, 2\not|\ n$”

Note that the original statement says “There is a natural number that is divisible by $2$.” The negation of this statement is therefore “No natural number is divisible by $2$” or, alternatively, in a way that indicates which quantifier to use, “For each natural number $n$, $2$ does NOT divide $n$.”

Negating Statements with Multiple Alternating Quantifiers.

Consider the statement

“$\forall x\in \mathbb{R}, \exists y \in \mathbb{R}$ such that $\forall z\in \mathbb{R}, x\leq y\leq z$.

How can we negate this monster? Simple! Start from the first quantifier and work your way in, negating as we did before when dealing with only one quantifier! The underlined in the worked example below indicates what is getting negated next as we work from the outermost quantifier to the inner predicate $x\leq y\leq z$.

$$\begin{align} & \neg \underline{(\forall x\in \mathbb{R}, \exists y \in \mathbb{R}\ \text{such that}\ \forall z\in \mathbb{R}, x\leq y\leq z)} \\ &\equiv \exists x\in \mathbb{R}\ \text{such that}\ \neg\underline{(\exists y \in \mathbb{R}\ \text{such that}\ \forall z\in \mathbb{R}, x\leq y\leq z)}\\ &\equiv \exists x\in \mathbb{R}\ \text{such that}\ \forall y \in \mathbb{R}, \ \neg\underline{(\forall z\in \mathbb{R}, x\leq y\leq z)}\\ &\equiv \exists x\in \mathbb{R}\ \text{such that}\ \forall y \in \mathbb{R}, \exists z\in \mathbb{R}\ \text{such that}\ \neg\underline{(x\leq y\leq z)}\\ &\equiv \exists x\in \mathbb{R}\ \text{such that}\ \forall y \in \mathbb{R}, \exists z\in \mathbb{R}\ \text{such that}\ (y<x\ or\ z<y)\end{align}$$

Negating Statements with Alternating Quantifiers

Let $P(x_1,x_2,x_3,x_4,x_5,x_6)$ be a predicate. The negation of statements with alternating quantifiers such as
“$\forall x_1\ \exists x_2\ \forall x_3\ \exists x_4\ \forall x_5\ \exists x_6\ P(x_1,x_2,x_3,x_4,x_5,x_6)$”
just switch each quantifier with its opposite, and negate the predicate $P(x_1,x_2,x_3,x_4,x_5,x_6)$.
Symbolically,
“\begin{align}&\neg(\forall x_1\ \exists x_2\ \forall x_3\ \exists x_4\ \forall x_5\ \exists x_6\ P(x_1,x_2,x_3,x_4,x_5,x_6)) \\ & \equiv \exists x_1\ \forall x_2\ \exists x_3\ \forall x_4\ \exists x_5\ \forall x_6\ \neg P(x_1,x_2,x_3,x_4,x_5,x_6)\end{align}”

CAVEAT: If you have the same quantifier repeated “in a row”, such as in a statement with the shape “$\forall x\ \forall y\ \forall z\ \exists a\ \forall b\ \exists c$”, before negating, it is advised to “compress” the repeated quantifiers so you don’t have the same quantifier repeated “in a row.” The shape just given compresses to a statement like “$\forall x,y,z\ \exists a\ \forall b\ \exists c$.”

“$\forall x\in \mathbb{N}, \forall y\in \mathbb{N}, \exists z\in\mathbb{N},$ such that $z\vert x$ and $z\vert y$”

“$\forall x,y\in \mathbb{N},\ \exists z\in\mathbb{N},$ such that $z\vert x$ and $z\vert y$”

Since we have two “for all’s” in a row, we can write that as a single “for all.” Furthermore, we don’t need to say “$\forall x\in \mathbb{N}, y\in \mathbb{N}…$” since both $x$ and $y$ live in the same set. While the latter isn’t wrong, and it does reduce the two “for all’s” down to a single “for all,” we can reduce the notation a bit more by writing “$\forall x,y\in \mathbb{N}$” since both $x$ and $y$ belong to the same set $\mathbb{N}$.

“$\forall x\in \mathbb{R}, \exists y\in \mathbb{R}$ such that $\exists z\in \mathbb{N}$ such that $\forall a\in \mathbb{R}, \forall b\in \mathbb{R}$, $a<z<y\ or\ b>a>x$”

“$\forall x\in \mathbb{R}, \exists y\in \mathbb{R} and z\in \mathbb{N} $ such that $\forall a,b\in\mathbb{R}, a<z<y\ or\ b>a>x$”

Notice that the pair of existential quantifiers had variables in different sets, namely $y\in \mathbb{R}$ and $z\in \mathbb{N}$. To handle this, we write the single existential quantifier out in front and simply state $y\in \mathbb{R}$ and $z\in \mathbb{N}$. Since the two “for all’s” quantified two variables living in the same set, we can further contract our notation by simply saying $\forall a,b\in \mathbb{R}$ as opposed to $\forall a\in \mathbb{R}, and\ b\in \mathbb{R}$.

Overall, don’t think too much about “following the rules” or modeling your own work on the examples you see here. Instead, think about how to simply reduce the amount of notation being used without losing any of the meaning that statements are trying to convey.

“$\forall x\in \mathbb{Z}, x\in \mathbb{Q}$”
“$\exists a\in \mathbb{Z},$ such that $a\vert 5$”
“$\forall a\in \mathbb{Z}, \exists b\in \mathbb{Z}$ such that $b\vert a$”
“$\exists n\in \mathbb{Z}$ such that $\forall m\in \mathbb{Z}, n\vert m$”
“$\forall \epsilon\in \mathbb{R}, \exists \mu \in \mathbb{R}$ such that $ \forall \eta \in \mathbb{R}, \eta\cdot(\epsilon-\mu)=0$”

Original Statement	Negation
“$\forall x\in \mathbb{Z}, x\in \mathbb{Q}$”	“$\exists x\in \mathbb{Z}$ such that $x\notin \mathbb{Q}$”
“$\exists a\in \mathbb{Z},$ such that $a\vert 5$”	“$\forall a\in \mathbb{Z},\ a\not\| 5$”
“$\forall a\in \mathbb{Z}, \exists b\in \mathbb{Z}$ such that $b\vert a$”	“$\exists a\in \mathbb{Z}$ such that $\forall b \in \mathbb{Z},\ b\not\| a$”
“$\exists n\in \mathbb{Z}$ such that $\forall m\in \mathbb{Z}, n\vert m$”	“$\forall n\in \mathbb{Z}, \exists m\in \mathbb{Z}, n\not\| m$”
“$\forall \epsilon\in \mathbb{R}, \exists \mu \in \mathbb{R}$ such that $ \forall \eta \in \mathbb{R}, \eta\cdot(\epsilon-\mu)=0$”	“$\exists \epsilon \in \mathbb{R}$ such that $\forall \mu \in \mathbb{R}, \exists \eta \in \mathbb{R}$ such that $\eta\cdot(\epsilon-\mu)\neq 0$”

Working from left to right, simply flip the quantifiers (so that $\forall$ becomes $\exists$ and vice versa), and negate the predicate (i.e. the stuff after all quantifiers), involving all your variables at the end of the statement.

For example, negating a statement of the form $\forall a, \exists b,\forall c,\exists d,\ P(a,b,c,d)$ would give you $\exists a \forall b \exists c \forall d, \neg P(a,b,c,d)$, where your $P(a,b,c,d)$ is the ending predicate involving your variables as mentioned above.

“$\forall x\in \mathbb{Z}, x\vert\ 0$”
“$\exists n\in \mathbb{N},$ such that $n>-4$”
“$\forall x\in \mathbb{R}, \exists y\in \mathbb{Z}$ such that $x/y=1$”
“$\exists n \in \mathbb{N}$ such that $\forall m\in \mathbb{Z}, \exists q\in \mathbb{R}$ such that $n\vert m\cdot q$”

Original Statement	Negated Statement
“$\forall x\in \mathbb{Z}, x\vert 0$”	“$\exists x\in \mathbb{Z}, x\not\|0$”
“$\exists n\in \mathbb{N},$ such that $n>-4$”	“$\forall n\in \mathbb{N}, n\leq -4$”
“$\forall x\in \mathbb{R}, \exists y\in \mathbb{Z}$ such that $x/y=1$”	“$\exists x\in \mathbb{R}$ such that $\forall y \in \mathbb{Z}, x/y\neq 1$”
“$\exists n \in \mathbb{N}$ such that $\forall m\in \mathbb{Z}, \exists q\in \mathbb{R}$ such that $n\vert m\cdot q$”	“$\forall n \in \mathbb{N}, \exists m \in \mathbb{Z}$ such that $\forall q\in \mathbb{R}$ such that $n\not\|\ m\cdot q$”

Statement 1: “$\forall n\in \mathbb{Z}, \exists m\in \mathbb{Z}$ such that $m=n$

Statement 2: “$\exists n \in \mathbb{Z}$ such that $\forall m \in \mathbb{Z}, m=n$”

nope!

The first statement says “no matter what integer $n$ I pick, I can find an integer equal to it”

The second statement says “There is some integer that is equal to all other integers.”

Clearly not equivalent. The is dissecting what each statement actually says and understanding it fully. I find it helpful to “personalize” quantifiers as I have above. For instance, instead of saying “for all ” or “for every”, I’d state it as “If I choose any…” For existential quantifiers, instead of saying “there is” or “there exists”, I tend to say “I can find.”

Practicing translating mathematical ideas into their simplest possible expression, in such a way that the idea can be understood easily by a non-mathematician, is arguably the best way to become an outstanding mathematician. That’s one reason why we bother with all of this loveliness! Helps you practice “cutting through the noise.”

Previous Topic

Back to Lesson

Next Lesson

Original Statement	Negation
“\(\forall x\in \mathbb{Z}, x\in \mathbb{Q}\)”	“\(\exists x\in \mathbb{Z}\) such that \(x\notin \mathbb{Q}\)”
“\(\exists a\in \mathbb{Z},\) such that \(a\vert 5\)”	“\(\forall a\in \mathbb{Z},\ a\not\| 5\)”
“\(\forall a\in \mathbb{Z}, \exists b\in \mathbb{Z}\) such that \(b\vert a\)”	“\(\exists a\in \mathbb{Z}\) such that \(\forall b \in \mathbb{Z},\ b\not\| a\)”
“\(\exists n\in \mathbb{Z}\) such that \(\forall m\in \mathbb{Z}, n\vert m\)”	“\(\forall n\in \mathbb{Z}, \exists m\in \mathbb{Z}, n\not\| m\)”
“\(\forall \epsilon\in \mathbb{R}, \exists \mu \in \mathbb{R}\) such that \( \forall \eta \in \mathbb{R}, \eta\cdot(\epsilon-\mu)=0\)”	“\(\exists \epsilon \in \mathbb{R}\) such that \(\forall \mu \in \mathbb{R}, \exists \eta \in \mathbb{R}\) such that \(\eta\cdot(\epsilon-\mu)\neq 0\)”

Original Statement	Negated Statement
“\(\forall x\in \mathbb{Z}, x\vert 0\)”	“\(\exists x\in \mathbb{Z}, x\not\|0\)”
“\(\exists n\in \mathbb{N},\) such that \(n>-4\)”	“\(\forall n\in \mathbb{N}, n\leq -4\)”
“\(\forall x\in \mathbb{R}, \exists y\in \mathbb{Z}\) such that \(x/y=1\)”	“\(\exists x\in \mathbb{R}\) such that \(\forall y \in \mathbb{Z}, x/y\neq 1\)”
“\(\exists n \in \mathbb{N}\) such that \(\forall m\in \mathbb{Z}, \exists q\in \mathbb{R}\) such that \(n\vert m\cdot q\)”	“\(\forall n \in \mathbb{N}, \exists m \in \mathbb{Z}\) such that \(\forall q\in \mathbb{R}\) such that \(n\not\|\ m\cdot q\)”