Page 84 - Discrete Mathematics and Its Applications

1.5 Nested Quantifiers 63

[Note that we can write this statement as ∀x∃!yB(x, y), where ∃! is the “uniqueness quantifier”
defined in Section 1.4.] ▲

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

Statements involving nested quantifiers can be negated by successively applying the rules for
negating statements involving a single quantifier. This is illustrated in Examples 14–16.

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 in Table 2 of
Section 1.4, we can move the negation in ¬Hx ∃y(xy = 1) inside all the quantifiers. We find
that ¬Hx ∃y(xy = 1) is equivalent to ∃x¬Py(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 ¬Pw ∀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 in Table 2
of Section 1.4 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¬Ha ∃f(P(w,f) ∧ Q(f, a)) ≡∀w∃a¬Pf(P( w,f) ∧ Q(f, a))
≡∀w∃a∀f ¬(P(w,f) ∧ Q(f, a))
≡∀w∃a∀f(¬P(w,f) ∨¬Q(f, a)).
This last statement states “For every woman there is an airline such that for all flights, this
woman has not taken that flight or that flight is not on this airline.” ▲