3.4 QUANTIFICATION OF PROPOSITIONAL FUNCTIONS IN SEVERAL VARIABLES 105y whose existence is being asserted, although not necessarily being uniquely
determined by x, depends - on x, as in the preceding example, where the
additive inverse of x = 6 is y = - 6, the inverse of x = - 7 is y = 7, if x = n,
then y = -n, and so on. If, in addition to (Vx)(3y)(p(x, y)), the stronger
statement (3y)(Vx)(p(x, y)) is also true [which may or not be the case, for a
given predicate p(x, y)], then this y does not depend on x; the object whose
existence is being asserted need not vary as x varies. Stated differently, there
is at least one specific value of y (y = 0 in the case of our "additive identity"
example) that makes p(x, y) true for every x.
An understanding of the difference, and the logical relationship, between
the mixed quantifiers (Vx)(3y) and (3y)(Vx) is crucial to much theoretical
work in upper-level undergraduate mathematics and is absolutely basic at
the graduate level. A special effort should be made to understand Theorem
1, the examples of the previous two paragraphs, and this final example.
EXAMPLE 3 Let U be the collection of all finite subsets, including 0, of the
set N of all positive integers. Define a propositional function s on U x U
by s(X, Y): X G Y. Analyze the four statements:Discussion Statement (a) says that, for every set X in the collection U (of
Jinite subsets of N), there corresponds some set Y in U that contains X
as a subset. Let us try some examples:
Given X = (1,2, 31, we could let Y = (1,2, 3,4).
Given X = ( l,2,... ,49,50), we could let Y = (l,2,... ,85,86). For
that matter, we could let Y = X, since every set is a subset of itself.
Given X = (2;... ; 999,999; 1,000,000), we may let Y = (2;... ;
2,000,000). Short of a formal proof, we seem to have good reason to
believe, from these examples, that statement (a) is true.
Statement (b) says that, to any set Y in U, there corresponds at least
one set X in- U that is a subset of Y. As in the previous para-
graph, given Y = (1; 2; 3;.. .; 1,000,000), we may let X = (1; 2; 3;... ;
999,999). If Y = (l;2;.. .; 50,0001, we may let X = (1;2;.. .; 10,000).
Or, if Y = (1,2, 3,4), we may let X = (1). Note that, as in the previous
paragraph, these choices of sets X, corresponding to a given set Y, are by
no means unique. In fact, see the discussion of (d), which follows, for
an entirely different approach.
The relationship between statements (c) and (a) is that discussed in
Theorem 1. Statement (c) is stronger than (a), a true statement, so that