Bridge to Abstract Mathematics: Mathematical Proof and Structures

98 LOGIC, PART II: THE PREDICATE CALCULUS Chapter 3

predicate -(p(x) + q(x)) is equivalent to (i.e., has the same truth set as)

Ax) A - q(x). Hence we have

where the latter is the desired form. If p(x) represents "x is a man" and

q(x) stands for "x is mortal," this equivalence indicates that "some men

are not mortal" is equivalent to the negation of "all men are mortal."

More generally, the negation of any statement of the form "every X is

a Y" can be expressed in the form "some X's are not Y's." This logical

principle has important implications for theorem-proving. Suppose we

wish to use proof by contrapositive [recall Theorem l(n), Article 2.31 to

prove a theorem whose conclusion is "every X is a Y." We would begin by

assuming the negation of that conclusion, that is, "there exists an X that is

not a Y." Another application of the principle occurs whenever we doubt

the truth of a conjecture "every X is a Y" and wish to prove it false. How

can we do this? The answer is: by showing that there exists an X that is

not a Y.

We conclude this article by returning to the paradox outlined in the

introduction to this chapter. Theorem 2 provides the means to resolve

it. Why is it not the case, for any two sets P and Q, that either P G Q

or Q c P when, for any x, the statement [(x E P) + (x E Q)] v [(x E Q)

+ (x E P)] is true? The answer is that "P c Q or Q G P" is symbolized in

the predicate calculus by (Vx)((x E P) + (x E Q)) v (Vx)((x E Q) + (x E P)).

As seen in Theorem 2(a), a statement of this form can be false even when

the corresponding statement (Vx)[((x E P) + (x E Q)) v ((x E Q) + (x E P))]

is true. Such is the case in this example.

Exercises

1. Express the logical negation of each of the following statements by a sentence
   beginning with "all" or "some," as appropriate:
   (a) All young women are athletes.
   (b) No young men are athletes.
   (c) Some women are young athletes.
   (d) All athletes are either young or are men.
   (e) Some athletes are young men.
   (f) If all athletes are young men, then no women are athletes.
   (g) Either all athletes are young women or some men are athletes.


2. (a) In parts (a) through (e) of Theorem 2, give examples different from those in
   Exercise 3, Article 3.2, of propositional functions, Ax) and q(x) over a domain
   U, for which the weaker statement form is true while the stronger one is false.
   (b) Is it possible to find such examples if we interchange the words "weaker" and
   "stronger" in (a)?