104 LOGIC, PART II: THE PREDICATE CALCULUS Chapter 3Solution Let U, x U, be the domain of discourse for p(x, y), and let P G
U, x U, be the truth set of p(x, y). Let us first examine (Vx)(3y)(p(x7 y)).
Let r(x) represent the one-variable propositional function (3y)(p(x, y) ).
Then an element u, E U, is in the truth set of r(x) if and only if (u,, y) E
P; that is, p(u,, y) is true, for some y E U,. Graphically, this means that
the set P must meet, or have nonempty intersection with, the "verti-
cal line" x = u,. The assertion (Vx)(r(x)), or (Vx)(3y)(p(x7 y)), therefore
means that P must meet every vertical line.
On the other hand, to analyze (3y)(Vx)(p(x, y)), let s(y) stand for one-
variable propositional function (Vx)(p(x, y)). An element 24, E U, is in
the truth set of s(y) if and only if (x, 24,) E P, that is, p(x, 24,) is true, for
every x E U,. Graphically, this means that the set P must contain the
"horizontal line" y = u, as a subset. The assertion (3y)(s(y)) or
(3y)(Vx)(p(x, y)) therefore means that the truth set P of p(x, y) must contain
some horizontal line.Suppose now that p(x, y) is the inequality of Example 1. Then Figure
3.la shows that (Vx)(3y)(x I y) is true; the "upper-triangular" region T
clearly meets every vertical line. But (3y)(Vx)(x < y) is false, because there
is no horizontal line entirely contained in T.
This example shows that (Vx)(3y)(p(x, y)) can be true while
(3y)(Vx)(p(x, y)) is false. But what if (3y)(Vx)(p(x, y)) is true? Then P con-
tains some "horizontal line" y = 24, (i.e., U, x (u,) c P). Consider an
arbitrary "vertical line" x = u,. This line must intersect P in at least one
point, namely (u,, u,) [i.e., (u,, u,) E ({u,} x Uz) n PI so that the statement
(Vx)(3y)(p(x, y)) must also be true.
Our conclusion from this discussion is expressed in the following theorem.THEOREM 1
For any propositional function p(x, y) in two variables,Thus any statement of the form (3y)(Vx)(p(x, y)) is stronger than the-- corresponding statement (Vx)(3y)(p(x7 y)). A familiar example of the first
form is the true assertion (3x)(Vy)(x + y = y), U = R, that an additive
identity (i.e., zero) exists for R. Note that, as Theorem 1 promises, the state-
ment (Vy)(3x)(x + y = y)Ys also true, where we may take x = 0 to corre-
spond to any given y. On the other hand, the proposition (Vx)(3y)(x + y = 0)
over R, which states that every real number has an additive inverse, or nega-
tive, has its corresponding proposition (3y)(Vx)(x + y = 0) false. For clearly
there does not exist a single value of y that is the additive inverse of
every x.
A statement (Vx)(3y)(p(x, y)), when true, asserts that, for any given x,
there is at least one corresponding y such that p(x, y) is true. As a rule, the