Discrete Mathematics: Elementary and Beyond

1.3 The Number of Subsets 9

1.2.13We form the union of two sets. We know that one of them hasnelements
and the other hasmelements. What can we infer about the cardinality of their
union?

1.2.14What is the intersection of

(a) the sets{ 0 , 1 , 3 }and{ 1 , 2 , 3 };

(b) the set of girls in this class and the set of boys in this class;

(c) the set of prime numbers and the set of even numbers?

1.2.15We form the intersection of two sets. We know that one of them hasn
elements and the other hasmelements. What can we infer about the cardinality
of their intersection?

1.2.16Prove (1.2), (1.3), and (1.4).

1.2.17Prove that|A∪B|+|A∩B|=|A|+|B|.

1.2.18 (a) What is the symmetric difference of the set
+of nonnegative in-

tegers and the setEof even integers (E={...,− 4 ,− 2 , 0 , 2 , 4 ,...}contains

both negative and positive even integers).

(b) Form the symmetric difference ofAandBto get a setC. Form the sym-

metric difference ofAandC. What did you get? Give a proof of the answer.

1.3 The Number of Subsets

Now that we have introduced the notion of subsets, we can formulate our
first general combinatorial problem: What is the number of all subsets of
a set withnelements?
We start with trying out small numbers. It makes no difference what the
elements of the set are; we call thema, b, cetc. The empty set has only
one subset (namely, itself). A set with a single element, say{a}, has two
subsets: the set{a}itself and the empty set∅. A set with two elements, say
{a, b}, has four subsets:∅,{a},{b}, and{a, b}. It takes a little more effort
to list all the subsets of a set{a, b, c}with 3 elements:

∅,{a},{b},{c},{a, b},{b, c},{a, c},{a, b, c}. (1.5)

We can make a little table from these data:

Number of elements 0 1 2 3

Number of subsets 1 2 4 8

Looking at these values, we observe that the number of subsets is a power
of 2: If the set hasnelements, the result is 2n, at least on these small
examples.