Bridge to Abstract Mathematics: Mathematical Proof and Structures

118 ELEMENTARY APPLICATIONS OF LOGIC Chapter 4

Beginning students often complain that the choose method doesn't seem

adequate to prove that every element of A is an element of B. After all,

we appear to be starting the proof by picking only one element of A. Such

an objection overlooks the power of universal quantification and, especially,

the fact that the "chosen x" is arbitrarily chosen. For those of you who

remain unconvinced, however, let us consider another way to justify the

choose method as a means of verifying the definition of AS BI suppose

we show, as in the proofs in Examples 4 and 5, that if x is an arbitrarily

chosen element of A, then x must lie in B. Then we have shown that there

is no x in A that does not lie in B, in symbols - [(3x)((x E A) A (x $ B))].

But this is logically equivalent, by Theorem l(b), Article 3.3, to

(Vx)[-((x E A) A (x # B))], which is equivalent to (Vx)[(x E A) -, (x E B)]

[cf., Theorem l(e), Article 2.31, the latter being the definition of "A is a subset

of B."

As the structure of theorems to be proved becomes more complex, so

do their proofs, as other techniques must be incorporated, along with the

basic elementhood approach.

EXAMPLE 6 Prove that A n (B u C) c (A n B) u C, where A, B, and C

are arbitrary sets.

Solution Let x E A n (B u C). To prove that x E (A n B) u C, we must

prove that either x E A n B or x E C. Suppose x $ C. We claim this ad-

ditional assumption forces the conclusion x E A n B. To show that x E

A n B, we must prove that x E A ad x E B. Now, by hypothesis, x E A

and x E B u C. Since x E A is true by assumption, only x E B remains

to be proved. Since x E B u C, then either x E B or x E C. Since x 4 C,

then x E B, as desired.

Note the approach we took (starting with "suppose x 4 C") to deduce

a conclusion whose logical form is q v r. You will recall the tautology

[p -+ (q v r)] * [(p A q) + r], discussed in Article 2.3 [Theorem l(p)]. To

prove that "one or the other" of two conclusions is true, we may take the

approach of assuming the negation of one of them and, on that basis, trying

to prove the other. We will discuss this technique in more detail in Article

6.2. Notice also that the argument in the last two sentences of the proof

was based on a tautology.- Can you identify it? (If not, see the last sentence

of the solution to Example 13.)

EXAMPLE 7 Prove that, for any sets A, B, and C, if A G B and B G C,
then A E C.
Solution To prove A E C, we must verify (Vx)[(x E A) + (x E C)], based
on the hypotheses A c B and B G C. We proceed by letting x be an
arbitrary element of A. We must show that x E C. We may argue as
I follows: Since x E A and A G B, then x E B. Since x E B and B r C,
then x E C, our desired conclusion. 0