Section 1.3 Quantifiers, Predicates, and Validity
41
In expressions such as (4x)P(x) or (E x)P(x), x is a dummy variable; that is, the
truth values of the expressions remain the same in a given interpretation if they
are written, say, as (4y)P( y) or (E z)P(z), respectively. Similarly, the truth value
of (4x)(E y)Q(x, y) is the same as that of (4z)(E w)Q(z, w) in any interpretation.
However, (4x)(E x)Q(x, x) says something quite different. In the interpretation of
Example 20, for instance, (4x)(E x)Q(x, x) says that for every integer x, there is an
integer x such that x < x. This statement is false, even though (4x)(E y)Q(x, y) was
true in this interpretation. We cannot collapse separate variables together into one
without changing the nature of the expression we obtain.
Constants are also allowed in expressions. A constant symbol (a, b, c, 0, 1, 2,
etc.) is interpreted as some specific object in the domain. This specification is part
of the interpretation. For example, the expression (4x)Q(x, a) is false in the interpretation where the domain consists of the integers, Q(x, y) is the property x < y,
and a is assigned the value 7; it is not the case that every integer is less than 7.
Now we can sum up what is required in an interpretation.
defInItIon inTerPreTaTion
An interpretation for an expression involving predicates consists of the following:
a. A collection of objects, called the domain of the interpretation, which must
include at least one object
b. An assignment of a property of the objects in the domain to each predicate in
the expression
c. An assignment of a particular object in the domain to each constant symbol in
the expression
Expressions can be built by combining predicates with quantifiers, grouping
symbols (parentheses or brackets), and the logical connectives of Section 1.1. As
before, an expression must obey rules of syntax to be considered a well-formed
formula. Well-formed formulas containing predicates and quantifiers are called
predicate wffs to distinguish them from propositional wffs, which contain only
statement letters and logical connectives.
The expression P(x)(4x) `)E y is not a well-formed formula. Examples of
predicate wffs are
P(x) ~ Q( y)
(1)
(4x)[P(x) S Q(x)]
(2)
(4x)((E y)[P(x, y) ` Q(x, y)] S R(x))
(3)
and
(E x)S(x) ~ (4y)T( y)
(4)
“Grouping symbols” such as parentheses and brackets identify the scope of a
quantifier, the section of the wff to which the quantifier applies. (This is analogous to the scope of an identifier in a computer program as the section of the
program in which that identifier has meaning.) There are no quantifiers in wff (1).
In (2), the scope of the quantifier (4x) is P(x) S Q(x). In (3), the scope of (E y) is
P(x, y) ` Q(x, y), while the scope of (4x) is the entire expression in parentheses
41
In expressions such as (4x)P(x) or (E x)P(x), x is a dummy variable; that is, the
truth values of the expressions remain the same in a given interpretation if they
are written, say, as (4y)P( y) or (E z)P(z), respectively. Similarly, the truth value
of (4x)(E y)Q(x, y) is the same as that of (4z)(E w)Q(z, w) in any interpretation.
However, (4x)(E x)Q(x, x) says something quite different. In the interpretation of
Example 20, for instance, (4x)(E x)Q(x, x) says that for every integer x, there is an
integer x such that x < x. This statement is false, even though (4x)(E y)Q(x, y) was
true in this interpretation. We cannot collapse separate variables together into one
without changing the nature of the expression we obtain.
Constants are also allowed in expressions. A constant symbol (a, b, c, 0, 1, 2,
etc.) is interpreted as some specific object in the domain. This specification is part
of the interpretation. For example, the expression (4x)Q(x, a) is false in the interpretation where the domain consists of the integers, Q(x, y) is the property x < y,
and a is assigned the value 7; it is not the case that every integer is less than 7.
Now we can sum up what is required in an interpretation.
defInItIon inTerPreTaTion
An interpretation for an expression involving predicates consists of the following:
a. A collection of objects, called the domain of the interpretation, which must
include at least one object
b. An assignment of a property of the objects in the domain to each predicate in
the expression
c. An assignment of a particular object in the domain to each constant symbol in
the expression
Expressions can be built by combining predicates with quantifiers, grouping
symbols (parentheses or brackets), and the logical connectives of Section 1.1. As
before, an expression must obey rules of syntax to be considered a well-formed
formula. Well-formed formulas containing predicates and quantifiers are called
predicate wffs to distinguish them from propositional wffs, which contain only
statement letters and logical connectives.
The expression P(x)(4x) `)E y is not a well-formed formula. Examples of
predicate wffs are
P(x) ~ Q( y)
(1)
(4x)[P(x) S Q(x)]
(2)
(4x)((E y)[P(x, y) ` Q(x, y)] S R(x))
(3)
and
(E x)S(x) ~ (4y)T( y)
(4)
“Grouping symbols” such as parentheses and brackets identify the scope of a
quantifier, the section of the wff to which the quantifier applies. (This is analogous to the scope of an identifier in a computer program as the section of the
program in which that identifier has meaning.) There are no quantifiers in wff (1).
In (2), the scope of the quantifier (4x) is P(x) S Q(x). In (3), the scope of (E y) is
P(x, y) ` Q(x, y), while the scope of (4x) is the entire expression in parentheses