106 LOGIC, PART II: THE PREDICATE CALCULUS Chapter 3
(c) may be either true or false. What does (c) assert? It says that there
is some set Y in U that contains every set X in U as a subset. Is there
a - single finite subset of N that contains - all finite subsets of N? You are
correct if your intuition tells you "no."
statement (d) is related to-(b) as (c) was related to (a). Again, since
(b) was true, (d) may be either true or false. We must now ask whether
there exists a single finite subset of N that is a subset of every finite
subset of N. Our answers in part (b) did not settle this question; for each
given Y, we gave back a corresponding X that changed as Y changed.
Was there some single subset X we could have given back in response to
every given Y? Yes! The empty set @ fulfills this role. Unlike (c), state-
ment (d) is true.
To summarize, (a) and (b) are both true but differ from each other in
a significant respect. Since (c) is false, the Y corresponding to a given X
in (a) must depend on (or vary with) that X. There is no single Y that works
for every given X. On the other hand, since (d) is true, then the X corre-
sponding to a given Y in (b) need not depend on Y. There exists a specific
set X, namely, X = @, that is a subset of every YE U.Theorem 1 has a generalization; here is a brief and informal description.
If p is a propositional function of more than two variables, say, p =
p(w, x, y, z), then Theorem 1 enables us to conclude (by an argument we
omit) that a statement such as (Vw)(3x)(Vy)(Vz)p(w, x, y, z) is stronger than
the corresponding statement (Vw)(Vy)(3x)(Vz)p(w, x, y, z). Note that the
statements are identical except that (3x) precedes (Vy) in the first statement,
whereas (Vy) precedes (3x) in the second. In the first statement, x depends
on w only; in the second, x depends on both w and y. Other examples of this
sort are found in Exercise 6, while an important application of this principle
to mathematical analysis is contained in Exercise 7, Article 4.3.
An analysis similar to that preceding Theorem 1 would convince us of
the following less difficult properties, which we summarize in the next
theorem.
THEOREM 2
Let p(x, y) be any propositional function in two variables. Then:
(4 (W (VY) P(X. Y) - (VY) (WP(X. Y)
(b) (~x)(~Y)P(x, Y) ++ (~Y)(WP(~I Y)
(c) (Vx)(Vy)p(x, y) + (3x)(3y)p(x, y), provided that each domain U, and U, is
nonempty.Theorem 2 generalizes to any finite number of variables. Parts (a) and
(b) say essentially that if only one quantifier is involved in a statement, the
order of quantification is of no consequence (unlike the situation with mixed
quantifiers). Part (c) generalizes (c) of Theorem 2, Article 3.3.