Page 82 - Discrete Mathematics and Its Applications

1.5 Nested Quantifiers 61

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)). ▲

One example that you may be familiar with is the concept of limit, which is important in
calculus.
EXAMPLE 8 (Requires calculus) 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

lim f(x) = L
x→a
is: 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

Expressions with nested quantifiers expressing statements in English can be quite complicated.
The first step in translating such an expression is to write out what the quantifiers and predicates
in the expression mean. The next step is to express this meaning in a simpler sentence. This
process is illustrated in Examples 9 and 10.

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))