Bridge to Abstract Mathematics: Mathematical Proof and Structures

96 LOGIC, PART II: THE PREDICATE CALCULUS Chapter 3

T H E 0 R E M 1 (Equivalences Involving Compound Predicates in One Variable)

Let p(x) and q(x) be predicates over a domain of discourse U with truth sets

P and Q. Then:

Statement about quantijied Corresponding statement

predicates about truth sets

(a) - [(Qx)(p(x))] t+ (3x)( -- p(x)) (a') P = U is false t+ P' # (21

(b) - [(3x)(p(x))] t+ (Vx)(--p(x)) (b') P # (21 is false - P' = U

(4 (WP(x) A dx)) '+ (Qx)(P(x)) (Vx)(q(x))

(c') PnQ= UoP=UandQ= U

(d) (3x)(p(x) v - (3xMx)) v (3x)(q(x))

(d) PuQZ(21-Pf 0orQZ0

Next, we apply the approach of Example 1 to another of the pairs of
quantified predicates from Exercise 3 [parts (e) and (f)], Article 3.2.

EXAMPLE 2 Describe in terms of truth sets the conditions under which the
quantified predicates (Vx)(h(x)) v (Vx)(k(x)) and (Vx)(h(x) v k(x)) are true.
Solution By Definition 2(b), the truth set of h(x) v k(x) is H u K. By Def-
inition 4(a), the universally quantified statement (Vx)(h(x) v k(x)) is true
if and only if H u K = U. On the other hand, by Definition 2(b), Article
2.1, (Vx)(h(x)) v (Vx)(k(x)) is true if and only if either (Vx)(h(x)) is true,
which means H = U, or (Vx)(k(x)) is true; that is, K = U. We conclude
that (Vx)(h(x)) v (Vx)(k(x)) is true if and only if either H = U or K = U.
0

Let us now compare the two conditions about sets arrived at in Example

2. Intuitively, it is clear that if either H = U or K = U, then H u K = U.
   What about the converse? Do we need either H = U or K = U in order
   to have H u K = U? The example U = R, H = Q, and K = Q' shows that
   the answer is "no." In this case the implication between the two statements
   from set theory goes in one direction only. Using transitivity of implication
   [Theorem 2(b), Article 2.31, we conclude that (Vx)(h(x)) v (Vx)(k(x)) implies
   (Vx)(h(x) v k(x)), by the argument

(Vx)(h(x)) v (Vx)(k(x)) is true t* (H = U) v (K = U)

-,HuK=U

* (Vx)(h(x) v k(x)) is true

As in the discussion following Example 1, this argument is based on the

assumption of a theorem from set theory that we have not, as yet, proved.

Thus it does not constitute a proof of the logical principle in question, but

only an arguvent that this principle is reasonable.

Our assertion that (Vx)(h(x)) v (Vx)(k(x)) implies (Vx)(h(x) v k(x)) means

that, for given predicates h(x) and k(x), the truth of the first statement implies