Discrete Mathematics for Computer Science

20 CHAPTER 1 Sets, Proof Templates, and Induction

Generalized Unions and Intersections

The definitions of union and intersection make good sense for any finite number of sets,

because the operations are associative. There are occasions, however, when one would

like to express the idea of the union of an infinite collection of sets. This leads to the

generalization of the notion of set union and intersection given in the next definition.

Definition 4. Let X be a set of sets. Then,

UX = {x x is contained in some set in X}

and

NX = {x x is contained in every set in X)

If

X = {X0, X1. Xn...

That is, the elements of X are indexed with the natural numbers, the union of sets UX is

usually written as

U7oXi = XO U X 1 U X 2 U ... U X, U ...

and the intersection of sets nX is usually written as

nr=oXi = X 0 n X 1 nX 2 n ... n X, n ...

Example 4.

(a) Ui = (-I/i, I/i) C JR where i E N - {0}. Then, UlUi = (-1, 1), NF1 =iUi = {o}.

(b) Vi = (i, i + 2) g R, where i ••N -{0}. Then, U?= Vi = (1, oo), N _.

1.3.2 Set Difference, Complements, and DeMorgan's Laws

In Venn diagrams, pairs of sets are often drawn so that it appears as if there are elements

in each of the sets that are not in the other set. Often, it is important to find these elements.

This operation on sets is called set difference. In other instances, we are interested in the

elements that are not in a set. The operation of finding these elements is called comple-

mentation. Finally, we would like to understand how union and intersection interact with

the operation of set difference and complementation. The relationships are described by

DeMorgan's Laws. We start this section by defining set difference.

Definition 5. Let A and B be sets. The set difference of A and B, denoted A - B, is

{x:x E A andx ý BI

U

0rA

B

Figure 1.9 A - B.