Page 62 - Discrete Mathematics and Its Applications

1.4 Predicates and Quantifiers 41

TABLE 1 Quantifiers.
Statement When True? When False?
∀xP (x) P(x) is true for every x. There is an x for which P(x) is false.
∃xP (x) There is an x for which P(x) is true. P(x) is false for every x.

EXAMPLE 8 Let P(x) be the statement “x + 1 >x.” What is the truth value of the quantification ∀xP (x),
where the domain consists of all real numbers?

Solution: Because P(x) is true for all real numbers x, the quantification

∀xP (x)

is true. ▲

Remark: Generally, an implicit assumption is made that all domains of discourse for quantifiers
are nonempty. Note that if the domain is empty, then ∀xP (x) is true for any propositional
function P(x) because there are no elements x in the domain for which P(x) is false.
Remember that the truth Besides “for all” and “for every,” universal quantification can be expressed in many other
value of ∀xP (x) depends
on the domain! ways, including “all of,” “for each,” “given any,” “for arbitrary,” “for each,” and “for any.”
Remark: It is best to avoid using “for any x” because it is often ambiguous as to whether “any”
means “every” or “some.” In some cases, “any” is unambiguous, such as when it is used in
negatives, for example, “there is not any reason to avoid studying.”

Astatement∀xP (x)isfalse,whereP(x)isapropositionalfunction,ifandonlyif P(x)isnot
always true when x is in the domain. One way to show thatP(x) is not always true when x is in the
domain is to find a counterexample to the statement ∀xP (x). Note that a single counterexample is
allweneedtoestablishthat∀xP (x)isfalse.Example9illustrateshowcounterexamplesareused.
EXAMPLE 9 Let Q(x) be the statement “x< 2.” What is the truth value of the quantification ∀xQ(x), where
the domain consists of all real numbers?

Solution: Q(x) is not true for every real number x, because, for instance, Q(3) is false. That is,
x = 3 is a counterexample for the statement ∀xQ(x). Thus

∀xQ(x)

is false. ▲

2
EXAMPLE 10 Suppose that P(x) is “x > 0.” To show that the statement ∀xP(x) is false where the uni-
verse of discourse consists of all integers, we give a counterexample. We see that x = 0is a
2
2
counterexample because x = 0 when x = 0, so that x is not greater than 0 when x = 0. ▲
Looking for counterexamples to universally quantified statements is an important activity
in the study of mathematics, as we will see in subsequent sections of this book.
When all the elements in the domain can be listed—say, x 1 , x 2 ,..., x n —it follows that the
universal quantification ∀xP(x) is the same as the conjunction

P(x 1 ) ∧ P(x 2 ) ∧ ··· ∧ P(x n ),

because this conjunction is true if and only if P(x 1 ), P(x 2 ),...,P(x n ) are all true.