Nested Quantifiers
Introduction: Nested quantifiers, are 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.
Nested quantifiers commonly occur in mathematics and computer science. Although nested quantifiers can sometimes be difficult to understand, In this section we will gain experience working with nested quantifiers.We will see how to use nested quantifiers to express mathematical statements such as “The sum of two positive integers is always positive.” We will show how nested quantifiers can be used to translate English sentences such as “Everyone has exactly one best friend” into logical statements. Moreover, we will gain experience working with the negations of statements involving nested quantifiers.
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, ifx > 0 andy < 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 knowthat ∃x∀yP(x, y) is true. If we never hit such an x, then we knowthat ∃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 involving more than one variable. 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. Be careful with the order
of existential and universal quantifiers!
