18 CHAPTER 1 Sets, Proof Templates, and Induction
Proof. The proofs are left as an exercise for the reader. U
The intersection of two sets may not contain any elements. If there are no elements in
a set intersection, we call the sets disjoint.
Definition 3. Let A and B be sets. Then, A and B are disjoint sets if A n B = 0.Example 3.
(a) Verify that {1, 2, 31 and 14, 5, 6} are disjoint.
(b) Verify that {1, 2, 31 and {{1, 2, 3}} are disjoint.
(c) For any set A, verify that A and 0 are disjoint.
The reader may be asking whether there is any reason or need to prove additional
theorems about the union and intersection operations on sets. There are two reasons to
prove additional theorems. First (and most obviously), the results will be needed later.
Second, proofs of these results are fairly easy examples of proofs, and they provide good
models for constructing other proofs. Additional opportunities to write proofs will be given
in the exercises.
Theorem 4 shows how set inclusion and the operations of union and intersection are
related.
Theorem 4. Let A, B, and C be sets. Then:(a) If AC B or AC C, then AC B U C.
(b) IfBCAandCCA, thenBUCCA.
(c) IfACBandA C, thenACBNC.
(d) IfBCAorCCA, thenBnCCA.
(Motivation for the proof.) For part (a), there are two cases: (i) A C B, and (ii) A C C.
The Venn diagrams (see Figure 1.7) illustrate both parts of (a) and will help in understand-
ing the proof.U U9D PFigurel.7 A.AcB • AcBUC. B.AcC • AcBuC.
For part (b), one Venn diagram suffices (see Figure 1.8).U
A