Quantifiers

Quantifiers
When the variables in a propositional function are assigned values, the resulting statement becomes a proposition with a certain truth value. However, there is another importantway, called quantification, to create a proposition from a propositional function. Quantification expresses the extent to which a predicate is true over a range of elements. In English, the words all, some, many, none, and few are used in quantifications. We will focus on two types of quantification here: universal quantification, which tells us that a predicate is true for every element under consideration, and existential quantification, which tells us that there is one or more element under consideration for which the predicate is true. The area of logic that deals with predicates and quantifiers is called the predicate calculus.

THE UNIVERSAL QUANTIFIER Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain. Such a statement is expressed using universal quantification. The universal quantification of P(x) for a particular domain is the proposition that asserts that P(x) is true for all values of x in this domain. Note that the domain specifies the possible values of the variable x. The meaning of the universal quantification of P(x) changes when we change the domain. The domain must always be specified when a universal quantifier is used; without it, the universal quantification of a statement is not defined.

DEFINITION 1 The universal quantification of P(x) is the statement “P(x) for all values of x in the domain.” The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the universal quantifier.We read ∀xP(x) as “for all xP(x)” or “for every xP(x).” An element for which P(x) is false is called a counterexample of ∀xP(x).

The meaning of the universal quantifier is summarized in the first row of Table 1. We illustrate the use of the universal quantifier in Examples 8–13.

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. Besides “for all” and “for every,” universal quantification can be expressed in many other 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) is false, whereP(x) is a propositional function, if and only ifP(x) is not always true when x is in the domain. Oneway to showthatP(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 allweneed to establish that ∀xP(x) is false

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.
Besides the phrase “there exists,”we can also express existential quantification in many other 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).”

The meaning of the existential quantifier is summarized in the second row of Table 1.

EXAMPLE 14 Let P(x) denote the statement “x > 3.” What is the truth value of the quantification ∃xP(x), where the domain consists of all real numbers?
Solution: Because “x > 3” is sometimes true—for instance, when x = 4—the existential quantification of P(x), which is ∃xP(x), is true.

Observe that the statement ∃xP(x) is false if and only if there is no element x in the domain for which P(x) is true. That is, ∃xP(x) is false if and only if P(x) is false for every element of the domain

THE UNIQUENESSQUANTIFIER We have now introduced universal and existential quantifiers. 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 ∃1xP(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 = 1 is the unique real number such that x − 1 = 0. Observe that we can use quantifiers and propositional logic to express uniqueness, 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.