Discrete Mathematics for Computer Science

16 CHAPTER 1 Sets, Proof Templates, and Induction

Example 1.

(a) 11, 2, 31 U 13, 4, 5) = 11, 2, 3, 3, 4, 5} = {1, 2, 3, 4, 5}.

(b) {1, 2, {1, 2, 3}} U {1, 2, 3, 11, 21) = {1, 2, 3, {1, 2}, {1, 2, 311.

(c) NUZ=Z.

(d) For any set A, A U 0 = A.

Why was the definition of the union of three or more sets not given? The more

general union operation, for any finite number of sets, is handled by the assumption that

A U B U C means (A U B) U C. Therefore, it is only necessary to find unions of two sets

at a time, and that has already been defined. The shaded region in Figure 1.5 shows the

union of three sets.

U

a

B

C

Figure 1.5 Au B U C.

The next theorem proves some fundamental results about set union.

Theorem 1. Let A, B, and C be sets. Then:

(a) AUA=A.

(b) ACAUBandBCAUB.

(c) A U B = B U A. (Commutative Law for Union)

(d) A U (B U C) = (A U B) U C. (Associative Law for Union)

(What the proof entails.) Parts (a) and (b) follow directly from the definition of union.

The proof of (c) will be given. Since the proof of (d) uses an argument similar to the one

used in (c), it will be left as an exercise for the reader. Part (c) says that the order in which

the union of two sets is formed does not matter. Part (d) states that A U B U C makes sense

even without parentheses.

Proof (c) Follow the template for set equality to prove that (i) A U B C B U A and (ii)

B U A C A U B. For (i), use the template for set inclusion to prove that for any x E A U B,

it follows that x E B U A.

Suppose that x e A U B. Then (ia) x e A or (ib) x E B. In case (ia), since x E A,

by Definition 1 we have x e B U A. In case (ib), since x E B, by Definition 1 we have

x e B U A. This completes the proof of (i).

The proof of (ii) is analogous. U

What do we mean when we say that one proof is analogous to another? In this context,

it means that the two proofs have essentially the same logic. Here, for example, one can

form the proof of part (ii) from the proof of part (i) by interchanging A and B.

The second important set operation, intersection, forms a set from the elements

common to two sets.