Discrete Mathematics for Computer Science

Operations on Sets 15

9. Describe in words the difference between 0 and {0}.


10. Let A, B, and C be sets.

(a) Prove that if A C B and B c C, then A C C.

(b) Prove that if A C B and B C C, then A C C.

(c) Prove that if A C B and A Z C, then B Z C.

rnOperations on Sets

In many areas of computer science and mathematics, from formal logic to object-oriented

programming, the operations to be performed must be considered in the context of a spe-

cific set. For example, familiar operations, such as addition, subtraction, multiplication,

and division, are performed within a specific set of numbers, such as the integers, ratio-

nals, or reals. This section discusses operations on sets and introduces the most common

operations: union, intersection, difference, complement, product, and power set of a set. We

study the laws these operations satisfy as well as how they interact with one another. We

then extend our discussion to lattices and boolean algebras. Lattices and boolean algebras

have two operations defined on their elements such that a set of special axioms for these

operations holds. An example of a lattice is a family of sets with the operations defined as

set union and set intersection.

1.3.1 Union and Intersection

The two simplest operations on sets involve combining two sets into one (union) and find-

ing common elements in two sets (intersection). These operations obey many of the gen-

eral rules that addition and multiplication with real numbers also satisfy. The first operation

consists of combining two sets into a set containing the elements of both sets.

Definition 1. Let A and B be sets. The union of A and B, denoted A U B, is

{x :x E A orx G B}

U

MA

B

Figure1.4 AUB.

The Venn diagram for set union (shown in Figure 1.4) illustrates what was stated in

the definition. We do, however, need to clarify the meaning of the word or in the definition.

When mathematicians say x E A or x E B, they generally mean x E A or x E B or both.

This interpretation is called the inclusive or because it includes the possibility that both

may be true.