Page 85 - Discrete Mathematics and Its Applications

64 1 / The Foundations: Logic and Proofs

EXAMPLE 16 (Requires calculus) Use quantifiers and predicates to express the fact that lim x→a f(x) does
not exist where f(x) is a real-valued function of a real variable x and a belongs to the domain
of f.

Solution: To say that lim x→a f(x) does not exist means that for all real numbers L,
lim x→a f(x) = L. By using Example 8, the statement lim x→a f(x) = L can be expressed as

¬H > 0 ∃δ>0 ∀x(0 < |x − a| <δ →|f(x) − L| < ).

Successively applying the rules for negating quantified expressions, we construct this sequence
of equivalent statements
¬H > 0 ∃δ>0 ∀x(0<|x − a|<δ →|f(x) − L|< )

≡∃ >0 ¬Pδ> 0 ∀x(0<|x − a|<δ →|f(x) − L|< )
≡∃ >0 ∀δ>0 ¬Hx( 0<|x − a|<δ →|f(x) − L|< )

≡∃ >0 ∀δ>0 ∃x ¬(0<|x − a|<δ →|f(x) − L|< )

≡∃ >0 ∀δ>0 ∃x(0<|x − a|<δ ∧|f(x) − L|≥ ).

In the last step we used the equivalence ¬(p → q) ≡ p ∧¬q, which follows from the fifth
equivalence in Table 7 of Section 1.3.
Because the statement “lim x→a f(x) does not exist” means for all real numbers L,
lim x→a f(x) = L, this can be expressed as

∀L∃ >0 ∀δ>0 ∃x(0 < |x − a| <δ ∧|f(x) − L|≥ ).

This last statement says that for every real number L there is a real number > 0 such that
for every real number δ> 0, there exists a real number x such that 0 < |x − a| <δ and
|f(x) − L|≥ . ▲

Exercises

1. TranslatethesestatementsintoEnglish,wherethedomain at your school. Express each of these quantifications in
for each variable consists of all real numbers. English.
a) ∀x∃y(x < y) a) ∃x∃yP(x, y) b) ∃x∀yP(x, y)
b) ∀x∀y(((x ≥ 0) ∧ (y ≥ 0)) → (xy ≥ 0)) c) ∀x∃yP(x, y) d) ∃y∀xP(x, y)
c) ∀x∀y∃z(xy = z) e) ∀y∃xP(x, y) f) ∀x∀yP(x, y)
2. TranslatethesestatementsintoEnglish,wherethedomain 5. Let W(x, y) mean that student x has visited website y,
for each variable consists of all real numbers. where the domain for x consists of all students in your
a) ∃x∀y(xy = y) school and the domain for y consists of all websites. Ex-
b) ∀x∀y(((x ≥ 0) ∧ (y < 0)) → (x − y> 0)) press each of these statements by a simple English sen-
c) ∀x∀y∃z(x = y + z) tence.
3. Let Q(x, y) be the statement “x has sent an e-mail mes- a) W(Sarah Smith, www.att.com)
sage to y,” where the domain for both x and y consists of b) ∃xW(x, www.imdb.org)
all students in your class. Express each of these quantifi- c) ∃yW(José Orez, y)
cations in English. d) ∃y(W(Ashok Puri, y) ∧ W(Cindy Yoon, y))
a) ∃x∃yQ(x, y) b) ∃x∀yQ(x, y) e) ∃y∀z(y = (David Belcher) ∧ (W(David Belcher, z)
c) ∀x∃yQ(x, y) d) ∃y∀xQ(x, y) → W(y,z)))
e) ∀y∃xQ(x, y) f) ∀x∀yQ(x, y) f) ∃x∃y∀z((x = y) ∧ (W(x, z) ↔ W(y, z)))
4. Let P(x, y) be the statement “Student x has taken class 6. Let C(x, y) mean that student x is enrolled in class y,
y,” where the domain for x consists of all students in your where the domain for x consists of all students in your
class and for y consists of all computer science courses school and the domain for y consists of all classes being