Page 79 - Discrete Mathematics and Its Applications

58 1 / The Foundations: Logic and Proofs

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

Many mathematical statements involve multiple quantifications of propositional functions in-
volvingmorethanonevariable.Itisimportanttonotethattheorderofthequantifiersisimportant,
unless all the quantifiers are universal quantifiers or all are existential quantifiers.
These remarks are illustrated by Examples 3–5.
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,