Mathematics for Computer Science

4.1. Sets 83

 TheintersectionofAandB, denotedA\B, consists of all elements that

appear inbothAandB. That is,

x 2 A\B IFF x 2 AANDx 2 B:

So,X\Y Df2;3g.

 Theset differenceofAandB, denotedAB, consists of all elements that

are inA, but not inB. That is,

x 2 AB IFF x 2 AANDx...B:

So,XY Df 1 gandYXDf 4 g.

Often all the sets being considered are subsets of a known domain of discourse,
D. Then for any subset,A, ofD, we defineAto be the set of all elements ofDnot
inA. That is,
AWWDDA:

The setAis called thecomplementofA. So

AD; IFFADD:

For example, if the domain we’re working with is the integers, the complement
of the nonnegative integers is the set of negative integers:

NDZ:

We can use complement to rephrase subset in terms of equality

ABis equivalent toA\BD;:

4.1.3 Power Set

The set of all the subsets of a set,A, is called thepower set, pow.A/, ofA. So

B 2 pow.A/ IFF BA:

For example, the elements of pow.f1;2g/are;;f 1 g;f 2 gandf1;2g.
More generally, ifAhasnelements, then there are 2 nsets in pow.A/—see The-
orem 4.5.5. For this reason, some authors use the notation 2 Ainstead of pow.A/.