Page 80 - Discrete Mathematics and Its Applications

1.5 Nested Quantifiers 59

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. ▲
Be careful with the order
of existential and Example 4 illustrates that the order in which quantifiers appear makes a difference.The state-
universal quantifiers!
ments ∃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.
(See Supplementary Exercises 30 and 31.)
Table 1 summarizes the meanings of the different possible quantifications involving two
variables.
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,”