2.4: Introduction to Quantification

In this section and the next, we introduce first-order logic—also referred to as predicate logic, quantificational logic, and first-order predicate calculus. The sentence “x > 0” is not itself a proposition because its truth value depends on x. In this case, we say that x is a free variable. A sentence with at least one free variable is called a predicate (or open sentence). To turn a predicate into a proposition, we must either substitute values for each free variable or “quantify” the free variables. We will use notation such as \(P (x)\) and \(Q(a,b)\) to represent predicates with free variables x and a,b, respectively. The letters “P ” and “Q” that we used in the previous sentence are not special; we can use any letter or symbol we want. For example, each of the following represents a predicate with the indicated free variables.

• S(x) B “x2 − 4 = 0”
• L(a,b) B “a < b”
• F(x,y) B “x is friends with y”

Note that we used quotation marks above to remove some ambiguity. What would S(x) = x² − 4 = 0 mean? It looks like S(x) equals 0, but actually we want S(x) to represent the whole sentence “x² − 4 = 0”. Also, notice that the order in which we utilize the free variables might matter. For example, compare L(a,b) with L(b,a).

One way we can make propositions out of predicates is by assigning specific values to the free variables. That is, if P (x) is a predicate and x0 is specific value for x, then P (x0 ) is now a proposition that is either true or false.

Problem 2.58. Consider S(x) and L(a,b) as defined above. Determine the truth values of S(0), S(−2), L(2,1), and L(−3,−2). Is L(2,b) a proposition or a predicate?

Besides substituting specific values for free variables in a predicate, we can also make a claim about which values of the free variables apply to the predicate.

Problem 2.59. Both of the following sentences are propositions. Decide whether each is true or false. What would it take to justify your answers?

(a) For all x ∈ R, x² − 4 = 0.

(b) There exists x ∈ R such that x² − 4 = 0.

Definition 2.60. “For all” is the universal quantifier and “there exists. . . such that” is the existential quantifier.

In mathematics, the phrases “for all”, “for any”, “for every”, and “for each” can be used interchangeably (even though they might convey slightly different meanings in colloquial language). We can replace “there exists. . . such that” with phrases like “for some” (possibly with some tweaking of the wording of the sentence). It is important to note that the existential quantifier is making a claim about “at least one”, not “exactly one.”

Variables that are quantified with a universal or existential quantifier are said to be bound. To be a proposition, all variables of a predicate must be bound.

We must take care to specify the collection of acceptable values for the free variables. Consider the sentence “For all x, x > 0.” Is this sentence true or false? The answer depends on what set the universal quantifier applies to. Certainly, the sentence is false if we apply it for all x ∈ Z. However, the sentence is true for all x ∈ N. Context may resolve ambiguities, but otherwise, we must write clearly: “For all x ∈ Z, x > 0” or “For all x ∈ N, x > 0.” The collection of intended values for a variable is called the universe of discourse.

Problem 2.61. Suppose our universe of discourse is the set of integers.

(a) Provide an example of a predicate P (x) such that “For all x, P (x)” is true.

(b) Provide an example of a predicate Q(x) such that “For all x, Q(x)” is false while “There exists x such that Q(x)” is true.

If a predicate has more than one free variable, then we can build propositions by quantifying each variable. However, the order of the quantifiers is extremely important!

Problem 2.62. Let P (x,y) be a predicate with free variables x and y in a universe of discourse U. One way to quantify the variables is “For all x ∈ U, there exists y ∈ U such that P (x,y).” How else can the variables be quantified?

The next problem illustrates that at least some of the possibilities you discovered in the previous problem are not equivalent to each other.

Problem 2.63. Suppose the universe of discourse is the set of people and consider the predicate M(x,y) B “x is married to y”. We can interpret the formal statement “For all x, there exists y such that M(x,y)” as meaning “Everybody is married to somebody.” Interpret the meaning of each of the following statements in a similar way.

(a) For all x, there exists y such that M(x,y).

(b) There exists y such that for all x, M(x,y).

(c) For all x, for all y, M(x,y).

(d) There exists x such that there exists y such that M(x,y).

Problem 2.64. Suppose the universe of discourse is the set of real numbers and consider the predicate F(x,y) B “x = y² ”. Interpret the meaning of each of the following statements.

(a) There exists x such that there exists y such that F(x,y).

(b) There exists y such that there exists x such that F(x,y).

(c) For all y, for all x, F(x,y).

There are a couple of key points to keep in mind about quantification. To be a proposition, all variables must be quantified. This can happen in at least two ways:

• The variables are explicitly bound by quantifiers in the same sentence.
• The variables are implicitly bound by preceding sentences or by context. Statements of the form “Let x = ...” and “Assume x ∈ ...” bind the variable x and remove ambiguity.

Also, the order of the quantification is important. Reversing the order of the quantifiers can substantially change the meaning of a proposition.

Quantification and logical connectives (“and,” “or,” “If. . . , then. . . ,” and “not”) enable complex mathematical statements. For example, if f is a function while c and L are real numbers, then the formal definition of lim_x→c f (x) = L, which you may have encountered in calculus, is:

For all ε > 0, there exists δ > 0 such that for all x, if 0 < |x − c| < δ, then |f (x) − L| < ε.

In order to study the abstract nature of complicated mathematical statements, it is useful to adopt some notation.

Definition 2.65. The universal quantifier “for all” is denoted \(∀\), and the existential quantifier “there exists. . . such that” is denoted \(∃\).

Using our abbreviations for the logical connectives and quantifiers, we can symbolically represent mathematical propositions. For example, the (true) proposition “There exists x ∈ R such that x2 −1 = 0” becomes “(∃x ∈ R)(x2 −1 = 0),” while the (false) proposition “For all x ∈ N, there exists y ∈ N such that y < x” becomes “(∀x ∈ N)(∃y ∈ N)(y < x).”

Problem 2.66. Convert the following propositions into statements using only logical and mathematical symbols. Assume that the universe of discourse is the set of real numbers.

(a) There exists x such that x² + 1 is greater than zero.

(b) There exists a natural number n such that n² = 36.

(c) For every x, x² is greater than or equal to zero.

Problem 2.67. Express the formal definition of a limit (given above Definition 2.65) in logical and mathematical symbols.

If you look closely, many of the theorems that we have encountered up until this point were of the form A(x) =⇒ B(x), where A(x) and B(x) are predicates. For example, consider

Theorem 2.2, which states, “If n is an even integer, then n2 is an even integer.” In this case, “n is an even integer” and “n2 is an even integer” are both predicates. So, it would be reasonable to assume that the entire theorem statement is a predicate. However, it is standard practice to interpret the sentence A(x) =⇒ B(x) to mean (∀x)(A(x) =⇒ B(x)) (where the universe of discourse for x needs to be made clear). We can also retool such statements to “hide” the implication. In particular, (∀x)(A(x) =⇒ B(x)) has the same meaning as (∀x ∈ U0 )B(x), where U0 is the collection of items from the universe of discourse U that makes A(x) true. For example, we could rewrite the statement of Theorem 2.2 as “For every even integer n, n² is even.”

Problem 2.68. Reword Theorem 2.7 so that it explicitly reads as a universally quantified statement. Compare with Problem 2.47.

Problem 2.69. Find at least two other instances of theorem statements that appeared earlier in the book and are written in the form A(x) =⇒ B(x). Rewrite each in an equivalent way that makes the universal quantifier explicit while possibly suppressing the implication.

Problem 2.70. Consider the proposition “If ε > 0, then there exists N ∈ N such that 1/N < ε.” Assume the universe of discourse is the set R.

(a) Express the statement in logical and mathematical symbols. Is the statement true?

(b) Reverse the order of the quantifiers to get a new statement. Does the meaning change? If so, how? Is the new statement true?

The symbolic expression (∀x)(∀y) can be abbreviated as \(∀x,y\) as long as x and y are elements of the same universe.

Problem 2.71. Express the proposition “For all x,y ∈ R with x < y, there exists m ∈ R such that x < m < y” using logical and mathematical symbols.

Problem 2.72. Rewrite each of the following propositions in words and determine whether the proposition is true or false.

(a) (∀n ∈ N)(n² ≥ 5)

(b) (∃n ∈ N)(n² − 1 = 0)

(c) (∃N ∈ N)(∀n > N)( \(\dfrac{1}{n}\) < 0.01)

(d) (∀m,n ∈ Z)((2|m ∧2|n) =⇒ 2|(m + n))

(e) (∀x ∈ N)(∃y ∈ N)(x − 2y = 0)

(f) (∃x ∈ N)(∀y ∈ N)(y ≤ x)

Problem 2.73. Consider the proposition (∀x)(∃y)(xy = 1).

(a) Provide an example of a universe of discourse where this proposition is true.

(b) Provide an example of a universe of discourse where this proposition is false.

To whet your appetite for the next section, consider how you might prove a true proposition of the form “For all x. . . .” If a proposition is false, then its negation is true. How would you go about negating a statement involving quantifiers?