3.1 BASIC CONCEPTS OF THE PREDICATE CALCULUS 83a statement p(5): 5 > 4 which happens to be true. If 2 is substituted for x,
we get p(2): 2 > 4, a false statement, but a statement nonetheless. The predi-
cate q(x, y): tan x = tan y, an example of a propositional function in two
variables, becomes a true statement when we substitute, for instance, 44
for x and 9n/4 for y.
Not all substitutions of specific objects for variables make a predicate
into a statement. For one thing, if we substitute n/4 for x in q(x, y), but
do not substitute for y, the resulting sentence q(n/4, y): tan n/4 = tan y is
still an open sentence, neither true nor false as it stands. In fact, p(y) =
q(n/4, y) is a propositional function in the single variable y. Thus, if we
wish to convert a predicate into a statement by substitution, we must take
care to substitute for each of the unknowns.
A second problem is that if we, for example, substitute the complex num-
ber -- 2 + 3i for x into the predicate p(x), we are left with a nonsense expres-
~ion 2 + 3i > 4. The same problem would occur (even more glaringly) if
we substituted an object other than a number, such as "John Smith" for
x. The message of these examples is one we saw in Chapter 1, in the con-
text of sets. Associated with each predicate p(x), there must be a universal
set U of objects that may be substituted for the variable. For the preceding
p(x), the set R of all real numbers would be a reasonable possibility for U,
whereas R x R could be the universal set for q(x, y). The set U, often re-
ferred to as the domain of discourse in the context of the predicate calculus,
is sometimes named explicitly and sometimes must be surmised, as was the
case with the concept of universal set in set theory.
For each open sentence p(x), with associated domain of discourse U, the
subset P of U defined by P = (x E U lp(x) is a true statement}, henceforth
described simply by (xlp(x)J, is called the truth set of p(x). As examples, if
U ,= R, the truth set of p(x): x > 4 is the interval (4, oo), whereas the subset
((x, y) E R x Rlx E domain (tan) and y = x + nx for some integer n) is the
truth set of q(x, y): tan x = tan y. As a matter of convention, we will adopt
the notation that truth sets of general predicates p(x), q(x, y), r(x, y, z) are
denoted by the corresponding uppercase letters P, Q, R, and the like.
We can use the idea of truth set to extend many of the concepts of the
propositional calculus to the predicate calculus. One example is provided
in the following definition.
DEFINITION- 1
We say that two propositional functions p(x) and q(x) (over a common domain
of discourse U) are logically equivalent over U if and only if they have the same
truth sets; that is, P = Q.Two predicates p(x) and q(x) may be equivalent over one domain of dis-
course and nonequivalent over another. For example, p(x, y): x2 = y2 and
q(x, y): x = y are equivalent over U, = R+ x R+, where R+ represents the
set of positive real numbers but are not 'equivalent over R x R. Just as
every propositional function determines a truth set, so is every set P the