Page 63 - Discrete Mathematics and Its Applications

42 1 / The Foundations: Logic and Proofs

2
EXAMPLE 11 What is the truth value of ∀xP (x), where P(x) is the statement “x < 10” and the domain
consists of the positive integers not exceeding 4?
Solution: The statement ∀xP (x) is the same as the conjunction

P(1) ∧ P(2) ∧ P(3) ∧ P(4),

because the domain consists of the integers 1, 2, 3, and 4. Because P(4), which is the statement
2
“4 < 10,” is false, it follows that ∀xP (x) is false. ▲
EXAMPLE 12 What does the statement ∀xN(x) mean if N(x) is “Computer x is connected to the network”
and the domain consists of all computers on campus?
Solution: The statement ∀xN(x) means that for every computer x on campus, that computer x
is connected to the network. This statement can be expressed in English as “Every computer on
campus is connected to the network.” ▲

As we have pointed out, specifying the domain is mandatory when quantifiers are used. The
truth value of a quantified statement often depends on which elements are in this domain, as
Example 13 shows.
2
EXAMPLE 13 What is the truth value of ∀x(x ≥ x) if the domain consists of all real numbers? What is the
truth value of this statement if the domain consists of all integers?
2
Solution: The universal quantification ∀x(x ≥ x), where the domain consists of all real num-
1
2
2
1 2
bers, is false. For example, ( ) ≥ . Note that x ≥ x if and only if x − x = x(x − 1) ≥ 0.
2 2
2
2
Consequently, x ≥ x if and only if x ≤ 0or x ≥ 1. It follows that ∀x(x ≥ x) is false if the
domain consists of all real numbers (because the inequality is false for all real numbers x with
2
0 <x < 1). However, if the domain consists of the integers, ∀x(x ≥ x) is true, because there
are no integers x with 0 <x < 1. ▲
THE EXISTENTIAL QUANTIFIER Many mathematical statements assert that there is an
element with a certain property. Such statements are expressed using existential quantification.
With existential quantification, we form a proposition that is true if and only if P(x) is true for
at least one value of x in the domain.
DEFINITION 2 The existential quantification of P(x) is the proposition

“There exists an element x in the domain such that P(x).”

We use the notation ∃xP (x) for the existential quantification of P(x). Here ∃ is called the
existential quantifier.

A domain must always be specified when a statement ∃xP(x) is used. Furthermore, the
meaning of ∃xP(x) changes when the domain changes. Without specifying the domain, the
statement ∃xP(x) has no meaning.
Besidesthephrase“thereexists,”wecanalsoexpressexistentialquantificationinmanyother
ways, such as by using the words “for some,” “for at least one,” or “there is.” The existential
quantification ∃xP(x) is read as
“There is an x such that P(x),”
“There is at least one x such that P(x),”

or
“For some xP(x).”