Discrete Mathematics for Computer Science

Operations on Sets 21

Example 5.

(a) Let A ={1, 2. 10} and B = {3, 5, 7, 9}. Then, A - B = {1, 2, 4, 6, 8, 101.

(b) Let A =N and B = {2i i E NJ. Then, A - B = {2i + 1: i E N}.

The difference A - B is also sometimes call the relative difference. The Venn dia-

gram (shown in Figure 1.9) gives an intuitive understanding of this notion. Remember that

Venn diagrams suggest relations between or among sets but are not actually proofs of rela-

tionships between or among sets. Theorem 6 proves some key relationships involving the

difference of two sets, A - B and B - A.

Theorem 6. Let A and B be sets. Then:

(a) A - B and B - A are disjoint, A - B and A n B are disjoint, and A n B and B - A

are disjoint.

(b) A=(A--B) U(ANB).

(c) AUB=(A-B) U(ANB) U (B - A).

(d) ACBifandonlyifA--B=0.

Proof. If you look at a Venn diagram for two sets and identify A - B, B - A, and A n B,

it looks like the sets are disjoint. This theorem says that your intuition from the diagram is

correct. The proofs of (a)-(d) are left as exercises for the reader. U

Complement of a Set

Recall that a universal set is a set that contains as a subset every set currently being dis-

cussed. In a context in which there is a universal set, another set theoretic operation can be

defined.

Definition 6. Let U be a universal set and A be a subset of U. The complement of A,

denoted A, is

{x : x E U andx ý A}

Sometimes, to emphasize that U is a universal set, A is also called the absolute difference.

With this definition, we can restate Definition 5 as A - B = A nf B. Some important

identities concern complements, especially how they interact with other set-theoretic oper-

ations.

Theorem 7. Let U be a universal set and A and B be subsets of U. Then:

(a) A = A. (A is the complement of A.)
(b) A C B if and only if B C A.
(c) A = B if and only if A = B.

(What the proof entails.) Part (a) tells us that the complement only produces something
new the first time it is applied. Part (b) says that if A is a subset of B, then set inclusion
goes the other way for the complements; that is, the complement of B is contained in the
complement of A. In part (c), we prove that if two sets are equal, then their complements
are equal.