Predicates and Quantification 137Solution.
(a) Vi E V (A[i] > 0)
(b) Vi e V (A[i] <A[30])
(c) Vi E V (A[i] 0) M
If V = 0, it is understood that Vx e V (S) is true and that Ix E V (S) is false, no matter
what S is.2.74 Nested Quantifiers
The formula 3x(3y(P(x, y))) contains nested quantifiers, with one quantifier inside the
parentheses marking the scope of the other. The obvious parentheses are usually omitted,
writing "3x3yP(x, y)." Since the two quantifiers are both 3's, you may also see "3x, y,
P(x, y)."
It is important to pay attention to the order of the quantifiers. Suppose P(x, y) is "x
received a higher grade on the exam than y did," and suppose U is the set of all students in
a class. To show that 3x(3y(P(x, y))), we start with the quantifier on the outside: We first
look for a student, x0 E U, to be represented by x. Now, we have a formula 3y(P(xo, y)).
Next, look for an object Yo E U to be represented by y. To show that the formula is true,
first pick an x0 who got a higher score, and then pick a yo who got a lower score.
If we meant to choose y first, we would write 3y(3x(P(x, y))). In this case, it does
not matter in which order we make the choices. One can see that the formula is true if and
only if not all students got the same score. Just pick x0 to be some student who got a higher
score than the score achieved by y. Since not all the scores are the same, it will always be
possible to make such choices.
To show with nested universal quantification that
Vx (Vy (x and y drive stick-shift cars and collect baseball cards))
is true, you must show that for all choices of x, and then for all choices of y, both x and y
drive stick-shift cars and collect baseball cards. In this case, again, the order of quantifiers
does not matter: The above is true if and only if Vy (Vx (x and y drive stick-shift cars and
collect baseball cards)) is true.
When the quantifiers switch between V and 3, the order becomes critically important.
To show that 3x (Vy (P(x, y))), you first pick a value for x0 for x from the universal set.
Then, you must show that no matter what value yo is chosen for y, P(xo, Yo) is true.
Example 4. Let P (x, y) denote x + y = 17, and let U be the set of integers. Show that
(a) Vx (3y (P(x, y))) is true.
(b) 3y (Vx (P(x, y))) is false.
Solution.
(a) First, x is specified as any integer. Now, you have to pick y to make P (x, y) true. For
example, pick y = 17 - x.
(b) To show this, you would have to pick a single yo so that for all x E U, x + yo = 17.
Since this must be true for all possible values of x, it must be true in particular for
x = 0 and x = 1-that is, for 0 + Yo = 17 and 1 + yo = 17. Those two cannot both
be true. 0