88 LOGIC, PART 11: THE PREDICATE CALCULUS Chapter 3
Quantification
It may have seemed surprising at the outset of Article 3.1 when we stated
that the equation A n (B u C) = (A n B) u (A n C) is an open sentence
rather than a statement. After all, we went to considerable trouble in Chap-
ter 1 (recall Example 3, ff., Article 1.3) to convince ourselves, Short of a
rigorous proof, that this equation is valid. So why then isn't it (strictly speak-
ing) a statement? The answer is that the statement discussed in Chapter 1
involves more than just the preceding equation. The law asserting that inter-
section distributes over union states that for every set A, for every set B,
and for every set C, the equation A n (B u C) = (A n B) u (A n C) is valid.
The expressions preceding the equation in the previous sentence are ex-
amples of the universal quantijer "for every," denoted by the symbol V.
The symbolized statement corresponding to the distributive law we dis-
cussed in Chapter 1 is
The universal quantifier is one of two quantifiers of the predicate calculus.
The other is the existential quantijier "there exists," denoted by the symbol
- A simple example of a statement involving the existential quantifier is
(3x)(5x - 3 = 0), U = R, a true assertion that the linear equation 5x - 3 =
0 has a real solution.
We now give a formal definition of the two quantifiers for the case of
open sentences in one variable. In this article and the next we will concen-
trate on the one-variable case. Quantification of propositional functions in
more than one variable will be considered in Article 3.4.
DEFINITION 1
If p(x) is a propositional function with variables x and domain of discourse U, then:(a) The sentence for all x, p(x), symbolized (Vx)(p(x)), is a proposition that is
true if and only if the truth set P of p(x) equals U.
(b) The sentence there exists x, p(x), symbolized (3x)(p(x)), is a proposition
that is true if and only if the truth set P of p(x) is nonempty.Certain features of Definition 1 deserve amplification. First, it is impor-
tant to understand that an expression (Vx)(p(x)) or (3x)(p(x)) is a proposi-
tion and not a propositional function, even though it involves a variable.
Unlike a propositional function, its truth value does not depend on the
variable x, but only on the propositional function p(x) and the domain of
discourse U. We might think of the variable x in a quantified predicate
as a "dummy variable," analogous to the role played by x in the definite
integral f(x)dx. Just as the name of the dummy variable makes no dif-
ference in a definite integral [so that Jh (x2 + x) dx = (y2 + y) dy, e.g.1,
so the name of the dummy variable is of no consequence in a quantified pre-
dicate [so that, e.g., (Vx)(x2 2 0) and (Vy)(y2 2 0) are the same statement].