Nested Quantifiers

Nested quantifiers are where one quantifier is within the scope of another, such as

∀x∃y(x + y = 0).

Note that everything within the scope of a quantifier can be thought of as a propositional function.
For example, ∀x∃y(x + y = 0) is the same thing as ∀xQ(x), where Q(x) is ∃yP(x, y), where P(x,
y) is x + y = 0.

Understanding Statements Involving Nested Quantifiers

To understand statements involving nested quantifiers, we need to unravel what the quantifiers
and predicates that appear mean. This is illustrated in Examples 1 and 2.

Example 1: Assume that the domain for the variables x and y consists of all real numbers. The
statement ∀x∀y(x + y = y + x) says that x + y = y + x for all real numbers x and y. This is the
commutative law for addition of real numbers. Likewise, the statement ∀x∃y(x + y = 0) says that
for every real number x there is a real number y such that x + y = 0. This states that every real
number has an additive inverse. Similarly, the statement ∀x∀y∀z(x + (y + z) = (x + y) + z) is the
associative law for addition of real numbers.

Example 2: Translate into English the statement ∀x∀y((x > 0) ∧ (y < 0) → (xy < 0)), where the
domain for both variables consists of all real numbers.

Solution: This statement says that for every real number x and for every real number y, if x > 0 and
y < 0, then xy < 0. That is, this statement says that for real numbers x and y, if x is positive and y is
negative, then xy is negative. This can be stated more succinctly as “The product of a positive real
number and a negative real number is always a negative real number.”

THINKING OF QUANTIFICATION AS LOOPS

In working with quantifications of more than one variable, it is sometimes helpful to think in terms
of nested loops. (Of course, if there are infinitely many elements in the domain of some variable, we
cannot actually loop through all values. Nevertheless, this way of thinking is helpful in
understanding nested quantifiers.) For example, to see whether ∀x∀yP(x, y) is true, we loop
through the values for x, and for each x we loop through the values for y. If we find that P(x, y) is
true for all values for x and y, we have determined that ∀x∀yP(x, y) is true. If we ever hit a value x
for which we hit a value y for which P(x, y) is false, we have shown that ∀x∀yP(x, y) is false.

Similarly, to determine whether ∀x∃yP(x, y) is true, we loop through the values for x. For each x
we loop through the values for y until we find a y for which P(x, y) is true. If for every x we hit such
a y, then ∀x∃yP(x, y) is true; if for some x we never hit such a y, then ∀x∃yP(x, y) is false. To see
whether ∃x∀yP(x, y) is true, we loop through the values for x until we find an x for which P(x, y)
is always true when we loop through all values for y. Once we find such an x, we know that
∃x∀yP(x, y) is true. If we never hit such an x, then we know that ∃x∀yP(x, y) is false.

Finally, to see whether ∃x∃yP(x, y) is true, we loop through the values for x, where for each x we
loop through the values for y until we hit an x for which we hit a y for which P(x, y) is true. The
statement ∃x∃yP(x, y) is false only if we never hit an x for which we hit a y such that P(x, y) is
true.

The Order of Quantifiers

It is important to note that the order of the quantifiers is important, unless all the quantifiers are
universal quantifiers or all are existential quantifiers.

Example 3: Let P(x, y) be the statement “x + y = y + x.” What are the truth values of the
quantifications ∀x∀yP(x, y) and ∀y∀xP(x, y) where the domain for all variables consists of all
real numbers?

Solution: The quantification ∀x∀yP(x, y) denotes the proposition “For all real numbers x, for all
real numbers y, x + y = y + x.” Because P(x, y) is true for all real numbers x and y (it is the
commutative law for addition, which is an axiom for the real numbers—see Appendix 1), the
proposition ∀x∀yP(x, y) is true. Note that the statement ∀y∀xP(x, y) says “For all real numbers
y, for all real numbers x, x + y = y + x.” This has the same meaning as the statement “For all real
numbers x, for all real numbers y, x + y = y + x.” That is, ∀x∀yP(x, y) and ∀y∀xP(x, y) have the
same meaning, and both are true. This illustrates the principle that the order of nested universal
quantifiers in a statement without other quantifiers can be changed without changing the meaning
of the quantified statement.

Example 4: Let Q(x, y) denote “x + y = 0.” What are the truth values of the quantifications
∃y∀xQ(x, y) and ∀x∃yQ(x, y), where the domain for all variables consists of all real numbers?

Solution: The quantification ∃y∀xQ(x, y) denotes the proposition “There is a real number y such
that for every real number x, Q(x, y).” No matter what value of y is chosen, there is only one value of
x for which x + y = 0. Because there is no real number y such that x + y = 0 for all real numbers x,
the statement ∃y∀xQ(x, y) is false.

The quantification ∀x∃yQ(x, y) denotes the proposition “For every real number x there is a real
number y such that Q(x, y).” Given a real number x, there is a real number y such that x + y = 0;
namely, y = −x. Hence, the statement ∀x∃yQ(x, y) is true.

REMARK: Example 4 illustrates that the order in which quantifiers appear makes a difference. The
statements ∃y∀xP(x, y) and ∀x∃yP(x, y) are not logically equivalent. The statement ∃y∀xP(x,
y) is true if and only if there is a y that makes P(x, y) true for every x. So, for this statement to be
true, there must be a particular value of y for which P(x, y) is true regardless of the choice of x. On
the other hand, ∀x∃yP(x, y) is true if and only if for every value of x there is a value of y for which
P(x, y) is true. So, for this statement to be true, no matter which x you choose, there must be a value
of y (possibly depending on the x you choose) for which P(x, y) is true. In other words, in the
second case, y can depend on x, whereas in the first case, y is a constant independent of x. From
these observations, it follows that if ∃y∀xP(x, y) is true, then ∀x∃yP(x, y) must also be true.
However, if ∀x∃yP(x, y) is true, it is not necessary for ∃y∀xP(x, y) to be true.

Quantifications of more than two variables are also common, as Example 5 illustrates.

Example 5: Let Q(x, y, z) be the statement “x + y = z.” What are the truth values of the statements
∀x∀y∃zQ(x, y, z) and ∃z∀x∀yQ(x, y, z), where the domain of all variables consists of all real
numbers?

Solution: Suppose that x and y are assigned values. Then, there exists a real number z such that
x + y = z. Consequently, the quantification ∀x∀y∃zQ(x, y, z), which is the statement “For all real
numbers x and for all real numbers y there is a real number z such that x + y = z,” is true. The order
of the quantification here is important, because the quantification ∃z∀x∀yQ(x, y, z), which is the
statement “There is a real number z such that for all real numbers x and for all real numbers y it is
true that x + y = z,” is false, because there is no value of z that satisfies the equation x + y = z for all
values of x and y.

Table 1 summarizes the meanings of the different possible quantifications involving two variables.

Translating Mathematical Statements into Statements Involving Nested Quantifiers

Example 6: Translate the statement “The sum of two positive integers is always positive” into a
logical expression.

Solution: To translate this statement into a logical expression, we first rewrite it so that the implied
quantifiers and a domain are shown: “For every two integers, if these integers are both positive,
then the sum of these integers is positive.” Next, we introduce the variables x and y to obtain “For
all positive integers x and y, x + y is positive.” Consequently, we can express this statement as
∀x∀y((x > 0) ∧ (y > 0) → (x +y > 0)), where the domain for both variables consists of all
integers. Note that we could also translate this using the positive integers as the domain. Then the
statement “The sum of two positive integers is always positive” becomes “For every two positive
integers, the sum of these integers is positive. We can express this as ∀x∀y(x +y > 0), where the
domain for both variables consists of all positive integers.

Example 7: Translate the statement “Every real number except zero has a multiplicative inverse.”
(A multiplicative inverse of a real number x is a real number y such that xy = 1.)

Solution: We first rewrite this as “For every real number x except zero, x has a multiplicative
inverse.” We can rewrite this as “For every real number x, if x _= 0, then there exists a real number
y such that xy = 1.” This can be rewritten as ∀x((x _= 0) → ∃y(xy = 1)).

Example 8: Use quantifiers to express the definition of the limit of a real-valued function f (x) of a
real variable x at a point a in its domain.

Solution: Recall that the definition of the statement

For every real number _ > 0 there exists a real number δ > 0 such that |f (x) − L| ≤ 𝜖 whenever

0 < |x − a| < δ.

This definition of a limit can be phrased in terms of quantifiers by

∀𝜖 ∃δ∀x(0 < |x − a| < δ → |f (x) − L| ≤ 𝜖), where the domain for the variables δ and _ consists of
all positive real numbers and for x consists of all real numbers.

This definition can also be expressed as

∀𝜖 >0 ∃δ>0 ∀x(0 < |x − a| < δ → |f (x) − L|≤ 𝜖 ) when the domain for the variables _ and δ
consists of all real numbers, rather than just the positive real numbers.

[Here, restricted quantifiers have been used. Recall that ∀x>0 P(x) means that for all x with x>0,
P(x) is true.]

Translating from Nested Quantifiers into English

Example 9: Translate the statement ∀x(C(x) ∨ ∃y(C(y) ∧ F(x, y))) into English, where C(x) is “x
has a computer,” F(x, y) is “x and y are friends,” and the domain for both x and y consists of all
students in your school.

Solution: The statement says that for every student x in your school, x has a computer or there is a
student y such that y has a computer and x and y are friends. In other words, every student in your
school has a computer or has a friend who has a computer.
Example 10: Translate the statement ∃x∀y∀z((F (x, y) ∧ F(x, z) ∧ (y ≠z)) →￢F(y,z)) into
English, where F(a,b) means a and b are friends and the domain for x, y, and z consists of all
students in your school.

Solution: We first examine the expression (F (x, y) ∧ F(x, z) ∧ (y ≠z)) →￢F(y, z). This expression
says that if students x and y are friends, and students x and z are friends, and furthermore, if y and z
are not the same student, then y and z are not friends. It follows that the original statement, which
is triply quantified, says that there is a student x such that for all students y and all students z other
than y, if x and y are friends and x and z are friends, then y and z are not friends. In other words,
there is a student none of whose friends are also friends with each other.

Translating English Sentences into Logical Expressions

We now address the translation of sentences whose translation into logical expressions required
the use of nested quantifiers.

Example 11: Express the statement “If a person is female and is a parent, then this person is
someone’s mother” as a logical expression involving predicates, quantifiers with a domain
consisting of all people, and logical connectives.

Solution: The statement “If a person is female and is a parent, then this person is someone’s
mother” can be expressed as “For every person x, if person x is female and person x is a parent, then
there exists a person y such that person x is the mother of person y.” We introduce the
propositional functions F(x) to represent “x is female,” P(x) to represent “x is a parent,” and M(x, y)
to represent “x is the mother of y.” The original statement can be represented as

∀x((F (x) ∧ P(x)) → ∃yM(x, y)).

Using the null quantification rule, we can move ∃y to the left so that it appears just after ∀x,
because y does not appear in F(x) ∧ P(x). We obtain the logically equivalent expression ∀x∃y((F
(x) ∧ P(x)) → M(x, y)).

Example 12: Express the statement “Everyone has exactly one best friend” as a logical expression
involving predicates, quantifiers with a domain consisting of all people, and logical connectives.

Solution: The statement “Everyone has exactly one best friend” can be expressed as “For every
person x, person x has exactly one best friend.” Introducing the universal quantifier, we see that this
statement is the same as “∀x(person x has exactly one best friend),” where the domain consists of
all people. To say that x has exactly one best friend means that there is a person y who is the best
friend of x, and furthermore, that for every person z, if person z is not person y, then z is not the
best friend of x. When we introduce the predicate B(x, y) to be the statement “y is the best friend of
x,” the statement that x has exactly one best friend can be represented as
∃y(B(x, y) ∧ ∀z((z _= y)→￢B(x, z))).
Consequently, our original statement can be expressed as
∀x∃y(B(x, y) ∧ ∀z((z _= y)→￢B(x, z))).
Example 13: Use quantifiers to express the statement “There is a woman who has taken a flight on
every airline in the world.”

Solution: Let P(w, f ) be “w has taken f ” and Q(f, a) be “f is a flight on a.”We can express the
statement as ∃w∀a∃f (P(w, f ) ∧ Q(f, a)), where the domains of discourse for w, f , and a consist
of all the women in the world, all airplane flights, and all airlines, respectively.

The statement could also be expressed as ∃w∀a∃fR(w, f, a), where R(w, f, a) is “w has taken f on
a.” Although this is more compact, it somewhat obscures the relationships among the variables.
Consequently, the first solution is usually preferable.

Negating Nested Quantifiers

Example 14: Express the negation of the statement ∀x∃y(xy = 1) so that no negation precedes a
quantifier.

Solution: By successively applying De Morgan’s laws for quantifiers, we can move the negation in
￢∀x∃y(xy = 1) inside all the quantifiers. We find that ￢∀x∃y(xy = 1) is equivalent to
∃x￢∃y(xy = 1), which is equivalent to ∃x∀y￢(xy = 1). Because ￢(xy = 1) can be expressed
more simply as xy _= 1, we conclude that our negated statement can be expressed as

∃x∀y(xy _= 1).

Example 15: Use quantifiers to express the statement that “There does not exist a woman who has
taken a flight on every airline in the world.”

Solution: This statement is the negation of the statement “There is a woman who has taken a flight
on every airline in the world” from Example 13. By Example 13, our statement can be expressed as
￢∃w∀a∃f (P(w, f ) ∧ Q(f, a)), where P(w, f ) is “w has taken f ” and Q(f, a) is “f is a flight on a.”
By successively applying De Morgan’s laws for quantifiers to move the negation inside successive
quantifiers and by applying De Morgan’s law for negating a conjunction in the last step, we find that
our statement is equivalent to each of this sequence of statements:

∀w￢∀a∃f (P(w, f ) ∧ Q(f, a)) ≡ ∀w∃a￢∃f (P(w, f ) ∧ Q(f, a))

Example 16: Use quantifiers and predicates to express the fact that

does not exist where f (x) is a real-valued function of a real variable x and a belongs to the domain
of f.