Page 155 - Discrete Mathematics and Its Applications

134 2 / Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

We can extend the notation we have introduced for unions and intersections to other families of
sets. In particular, we use the notation

∞

A 1 ∪ A 2 ∪ ··· ∪ A n ∪ ··· = A i
i=1

to denote the union of the sets A 1 ,A 2 ,...,A n ,... . Similarly, the intersection of these sets is
denoted by

∞

A 1 ∩ A 2 ∩ ··· ∩ A n ∩ ··· = A i .
i=1

More generally, when I is a set, the notations A i and A i are used to denote
i∈I i∈I

the intersection and union of the sets A i for i ∈ I, respectively. Note that we have A i =
i∈I

{x |∀i ∈ I(x ∈ A i )} and A i ={x |∃i ∈ I(x ∈ A i )}.
i∈I
EXAMPLE 17 Suppose that A i ={1, 2, 3,...,i} for i = 1, 2, 3,... . Then,
∞ ∞

A i = {1, 2, 3,...,i}={1, 2, 3,...}= Z +
i=1 i=1
and

∞ ∞

A i = {1, 2, 3,...,i}={1}.
i=1 i=1

To see that the union of these sets is the set of positive integers, note that every positive
integer n is in at least one of the sets, because it belongs to A n ={1, 2,...,n}, and every element
of the sets in the union is a positive integer. To see that the intersection of these sets is the set
{1}, note that the only element that belongs to all the sets A 1 ,A 2 ,... is 1. To see this note that
A 1 ={1} and 1 ∈ A i for i = 1, 2,.... ▲

Computer Representation of Sets

There are various ways to represent sets using a computer. One method is to store the elements
of the set in an unordered fashion. However, if this is done, the operations of computing the
union, intersection, or difference of two sets would be time-consuming, because each of these
operations would require a large amount of searching for elements. We will present a method
for storing elements using an arbitrary ordering of the elements of the universal set. This method
of representing sets makes computing combinations of sets easy.
Assume that the universal set U is finite (and of reasonable size so that the number of
elements of U is not larger than the memory size of the computer being used). First, specify an
arbitrary ordering of the elements of U, for instance a 1 ,a 2 ,...,a n . Represent a subset A of U
with the bit string of length n, where the ith bit in this string is 1 if a i belongs to A and is 0 if
a i does not belong to A. Example 18 illustrates this technique.

EXAMPLE 18 Let U ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in
increasing order; that is, a i = i. What bit strings represent the subset of all odd integers in U,
the subset of all even integers in U, and the subset of integers not exceeding 5 in U?