Page 65 - Discrete Mathematics and Its Applications

44 1 / The Foundations: Logic and Proofs
EXAMPLE 17
THE UNIQUENESS QUANTIFIER We have now introduced universal and existential quan-
tifiers. These are the most important quantifiers in mathematics and computer science. However,
there is no limitation on the number of different quantifiers we can define, such as “there are
exactly two,” “there are no more than three,” “there are at least 100,” and so on. Of these other
quantifiers, the one that is most often seen is the uniqueness quantifier, denoted by ∃! or ∃ 1 .
The notation ∃!xP (x) [or ∃ 1 xP (x)] states “There exists a unique x such that P(x) is true.”
(Other phrases for uniqueness quantification include “there is exactly one” and “there is one and
only one.”) For instance, ∃!x(x − 1 = 0), where the domain is the set of real numbers, states
that there is a unique real number x such that x − 1 = 0. This is a true statement, as x = 1isthe
unique real number such that x − 1 = 0. Observe that we can use quantifiers and propositional
logic to express uniqueness (see Exercise 52 in Section 1.5), so the uniqueness quantifier can
be avoided. Generally, it is best to stick with existential and universal quantifiers so that rules
of inference for these quantifiers can be used.
Quantifiers with Restricted Domains
An abbreviated notation is often used to restrict the domain of a quantifier. In this nota-
tion, a condition a variable must satisfy is included after the quantifier. This is illustrated in
Example 17. We will also describe other forms of this notation involving set membership in
Section 2.1.
2
3
2
What do the statements ∀x< 0 (x > 0), ∀y = 0 (y = 0), and ∃z> 0 (z = 2) mean, where
the domain in each case consists of the real numbers?
2
2
Solution:The statement ∀x< 0 (x > 0) states that for every real number x with x< 0, x > 0.
That is, it states “The square of a negative real number is positive.” This statement is the same
2
as ∀x(x < 0 → x > 0).
3
The statement ∀y = 0 (y = 0) states that for every real number y with y = 0, we have
3
y = 0. That is, it states “The cube of every nonzero real number is nonzero.” Note that this
3
statement is equivalent to ∀y(y = 0 → y = 0).
2
Finally, the statement ∃z> 0 (z = 2) states that there exists a real number z with z> 0
2
such that z = 2. That is, it states “There is a positive square root of 2.” This statement is
2
equivalent to ∃z(z > 0 ∧ z = 2). ▲
Note that the restriction of a universal quantification is the same as the universal quantifi-
2
cation of a conditional statement. For instance, ∀x< 0 (x > 0) is another way of expressing
2
∀x(x < 0 → x > 0). On the other hand, the restriction of an existential quantification is the
2
same as the existential quantification of a conjunction. For instance, ∃z> 0 (z = 2) is another
2
way of expressing ∃z(z > 0 ∧ z = 2).
Precedence of Quantifiers
The quantifiers ∀ and ∃ have higher precedence than all logical operators from propositional
calculus. For example, ∀xP(x) ∨ Q(x) is the disjunction of ∀xP(x) and Q(x). In other words,
it means (∀xP(x)) ∨ Q(x) rather than ∀x(P(x) ∨ Q(x)).
Binding Variables
When a quantifier is used on the variable x, we say that this occurrence of the variable is bound.
An occurrence of a variable that is not bound by a quantifier or set equal to a particular value
is said to be free. All the variables that occur in a propositional function must be bound or set
equal to a particular value to turn it into a proposition. This can be done using a combination of
universal quantifiers, existential quantifiers, and value assignments.