Discrete Mathematics for Computer Science

Operations on Sets 19

Proof. (a) Suppose that A C B or A C C.

Case 1: A C B. Follow Template 1.2 (Set Inclusion) for proving that one set is a subset

of another. Show that every element of A is also an element of B U C.

Let x E A. The goal is to show that x e B U C. Since x E A and A C B, we have

x E B. But,

BUC = {x x E B orx E C}

Therefore, x E B U C.

Case 2: A C C. The proof is analogous to that in part (a).

(b) Suppose x E B U C. Then, either x E B or x c C.

Case 1: x E B. Since B C A, it follows that x c A.

Case 2: x E C. Since C C A, it follows that x E A. Therefore, B U C C A.

(c)-(d) Exercises for the reader. M

The proof of Theorem 4 shows how a template can be used. It also demonstrates

another proof technique: proof by cases. The assumption was that A C B or A C C. The

proof breaks down into the two ways that this could happen: (1) A c B, or (2) A C C.

Each case was handled separately. This is a general approach: If there are relatively few

ways that some assumption can be met, then one can handle them separately.

Let's review what Theorem 4 asserts. Contrast the following two statements:

(a) "If A is a subset of both B and C, then A is a subset of their union."

IfA C BorA C C, thenA C BUC

(b) "If A is a subset of the union of B and C, then A is a subset of either B or C."

IfA C BUC, thenA C BorA CC

Theorem 4 asserts that statement (a) is true. Theorem 4 does not assert statement (b). In

fact, statement (b) is false in general. How would it be shown that statement (b) is false?

Statement (b) asserts that some relationship is true for all sets A, B, and C. To prove it to

be false, then, we must find just one example where it is false. That is, we must find three

sets A, B, and C such that A c B U C but (i) A Z B and (ii) A 7 C (see Exercise^9 in

Section 1.4).

The theorems proved so far can easily be used to show something that is not entirely

obvious.

Theorem 5. (An Absorption Law) Let A and B be sets. Then,

A U (A n B) = A

Proof As usual, prove that A U (A n B) C A and A C A U (A n B). For the first part,
we have A C A by Theorem 1 in Section 1.1.5 and A n B c A by Theorem 2(b) in Secton
1.3.1. These two conditions imply that A U (A n B) C A by Theorem 4(b) in Section 1.3.1.
For the second part, start with A C A, which gives A C A U (A n B) by Theorem 4(a) in
Section 1.3.1. U

This result is one that is needed later. When we discuss boolean algebras and their
relation to electrical circuits, this Absorption Law is particularly useful.