82 LOGIC, PART II: THE PREDICATE CALCULUS Chapter 3
to be saying "either P is a subset of Q or Q is a subset of P," which would
appear, thereby, always to be a true statement. But experience indicates
that this is not the case [see, in particular, Example 3(b), Article 1.11.
Our analysis apparently has led to a contradiction.The resolution to the paradox presented in Example 1 lies in the fact that
the two sentences symbolized earlier by p and q are not statements, but
rather, are open sentences or predicates, and furthermore, sentences such as
"P is a subset of Q" have an internal structure requiring the use of quanti-
Jiers (i.e., the expressions "for every" and "there exists") for logical accuracy.
In particular, one of the theorems of the predicate calculus to be studied
in this chapter provides the specific fact that will enable us to resolve the
paradox. We will return to this question following Theorem 2 and Example
3, Article 3.3.
Since most definitions and theorems in mathematics employ terms such
as "every" and "some" as well as the familiar "and," "or," and "if... then,"
most applications of logic to mathematics involve principles of both the
propositional calculus and predicate calculus, applied together in a single
setting. Armed with an understanding of the main tautologies of the prop-
ositional calculus and main theorems of the predicate calculus, students
who have also developed a working knowledge of their combined use (the
subject of Chapters 4,5, and 6) will be well prepared for the rigors of junior-
senior level mathematics and beyond!
Basic Concepts of the Predicate Calculus
Expressions such as "she is a doctor," "x2 - 3x - 40 = 0," and
"A n (B u C) = (A n B) u (A n C)," known as predicates, or propositional
functions (also known as open sentences), are the building blocks of the predi-
cate calculus. A predicate is a declarative sentence containing one or more
variables, or unknowns. As the preceding examples indicate, an unknown
may be a mathematical symbol, representing a number, a set, or some other
mathematical quantity. Additionally, it could be a pronoun, such as "he"
or "it," or for that matter, any other word with a variable meaning, like
"yesterday" or "tomorrow." A predicate is not a statement, since a predi-
cate is neither true nor false. On the other hand, predicates are closely re-
lated to statements, and our notation for them (e.g., p(~) or q(x, y), where
x and y are unknowns) reflects that fact. In particular, there are two stan-
dard procedures by which a predicate can be converted into a statement.
These procedures are substitution and quantification.
SUBSTITUTION, DOMAIN OF DISCOURSE, AND TRUTH SET
The sentence p(x): x > 4 is an example of a predicate; in fact, it is a predicate
in one variable. If the number 5 is substituted for x, the predicate becomes