Bridge to Abstract Mathematics: Mathematical Proof and Structures

I

90 LOGIC, PART It: THE PREDICATE CALCULUS Chapter 3

the word "some," and with sequences of words such as "there exists... such

that" or "there exists... for which."

The problem of appropriate English translation of quantified predicates

becomes more difficult when dealing with compound predicates.

EXAMPLE 2 Let U = Z. Let propositional functions p, q, r, and s be defined

over Z by

q(n): nisodd, Q={ ..., -5, -3, -1,1,3,5,...}

Analyze some compound predicates involving these open sentences.

Discussion (a) (Vn)(-p(n)) is the statement that "every integer is not

even" (false since P' # U), whereas -[(Vn)(p(n))] is the statement "it

is not the case that every integer is even" (true since (Vn)(p(n)) is false).

The symbolized statement (3n)( - p(n)) says that "some integers are not

even" (true since P' # @). What is the translation of -[(3n)(p(n))]?

Is this statement true or false? Do you see any connections among these

four statements?

(b) (3n)(r(n) A s(n)) is the statement that some integers are divisible

by 4 @by 3 (true since R nS= (..., -12,0, 12,24,36 ,... } #(a),

also intepretable as "some multiples of 4 are divisible by 3" or "some

multiples of 3 are divisible by 4." On the other hand, (3n)(p(n) A q(n))

("some even integers are odd) is false since P n Q = 0, but (3n)(p(n)) A

(3n)(q(n)) ("some integers are even and some integers are odd) is true,

because (3n)(p(n)) is true (P # 0) and (3n)(q(n)) is true (Q # 0).

(c) By (b), (3n)(r(n) A An)) symbolizes "some multiples of 4 are even."

How would we symbolize the (intuitively true) statement "every multiple

of 4 is even'? We might consider (Vn)(r(n) A (p(n)). But this translates to

"every integer is divisible by 4 and is even," clearly a false statement.

What we want to express is that an integer is even, if it is a multiple of 4.

"If" suggests the conditional; let us try (Vn)(r(n) -, An)). This translates

literally to "for every integer n, if n is a multiple of 4, then n is even,"

which seems to carry the same meaning as "every multiple of 4 is even."

Another test for possible equivalence is whether (Vn)(r(n) + An)) is true,

since we know intuitively that "every multiple of 4 is even" is true. Let

us try some substitutions for n; suppose n = 8. Since 48) and p(8) are

both true, so is 48) -, p(8). If n = 2, then 42) is false, p(2) is true, and so

r(2) -, p(2) is true. If n = 3, then r(3) and p(3) are both false, thus, again,

r(3) -+ p(3) is true. What case would make r(n) + p(n) false? We would