Page 150 - Discrete Mathematics and Its Applications

2.2 Set Operations 129

U U

A B A

A – B is shaded. A is shaded.

FIGURE 3 Venn Diagram for FIGURE 4 Venn Diagram for
the Difference of A and B. the Complement of the Set A.

Once the universal set U has been specified, the complement of a set can be defined.

DEFINITION 5 Let U be the universal set. The complement of the set A, denoted by A, is the complement
of A with respect to U. Therefore, the complement of the set A is U − A.

An element belongs to A if and only if x/∈ A. This tells us that

A ={x ∈ U | x/∈ A}.

In Figure 4 the shaded area outside the circle representing A is the area representing A.
We give some examples of the complement of a set.

EXAMPLE 8 Let A ={a, e, i, o, u} (where the universal set is the set of letters of the English alphabet). Then
A ={b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w,x,y,z}. ▲

EXAMPLE 9 Let A be the set of positive integers greater than 10 (with universal set the set of all positive
integers). Then A ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. ▲

It is left to the reader (Exercise 19) to show that we can express the difference of A and B
as the intersection of A and the complement of B. That is,

A − B = A ∩ B.

Set Identities

Table 1 lists the most important set identities. We will prove several of these identities here,
using three different methods. These methods are presented to illustrate that there are often many
different approaches to the solution of a problem. The proofs of the remaining identities will
Set identities and
be left as exercises. The reader should note the similarity between these set identities and the
propositional
equivalences are just logical equivalences discussed in Section 1.3. (Compare Table 6 of Section 1.6 and Table 1.) In
special cases of identities fact, the set identities given can be proved directly from the corresponding logical equivalences.
for Boolean algebra. Furthermore, both are special cases of identities that hold for Boolean algebra (discussed in
Chapter 12).
One way to show that two sets are equal is to show that each is a subset of the other. Recall
that to show that one set is a subset of a second set, we can show that if an element belongs to
the first set, then it must also belong to the second set. We generally use a direct proof to do this.
We illustrate this type of proof by establishing the first of De Morgan’s laws.