Let's apply some of our
knowledge about sets to counting finite sets. The size of a set S is called its
cardinality, which we'll denote by
|S|.
For example, if S = {a, b, c},
then |S| = | {a, b, c} | = 3. We can say "the cardinality of S is 3,"
or 3 is the cardinal number of S," or simply "S has three
elements."
Suppose we want to count the
union of two sets. For example, suppose we have A = {1, 2, 3, 4, 5} and B = { 2, 4, 6, 8}. Since
, it follows that
.
Similarly, since
, it follows that
. If we know any three of the four numbers |A|, |B|,
and
, then we can find the fourth by using the following counting
rule for finite sets:
Union Rule
(1.6)
It's easy to discover this
rule by drawing a Venn diagram.
The union rule extends to
three or more sets. For example, the following calculation gives the union rule
for three finite sets:
(1.7)
The popular name
for the union rule and its extensions to three or more sets is the principle of inclusion and exclusion.
The name is appropriate because the rule says to add (include) the count of
each individual set. Then subtract (exclude) the count of all intersecting
pairs of sets. Next, include the count of all intersections of three sets. Then
exclude the count of all intersections of four sets, and so on.
EXAMPLE 1 (A Building Project). Suppose A, B and Ñ are sets of tools needed by three workers on a job.
For convenience let's call the workers A, B, and C. Suppose further that the
workers share some of the tools (for example, on a housing project, all three
workers might share a single table saw). Suppose that A
uses 8 tools, B uses 10 tools, and C uses 5 tools. Suppose further that A and B
share 3 tools, A and C share 2 tools, and B and C share 2 tools. Finally,
suppose that A, B, and C share the use of 2 tools. How many distinct tools are
necessary to do the job? Thus we want to find the value
.
We can apply the inclusion
exclusion principle (1.7) to compute the answer:
EXAMPLE 2 (Surveys). Suppose we survey
200 students to see whether they are taking courses in computer science,
mathematics, or physics. The results show that 90 students take computer science,
110 take mathematics, and 60 take physics. Further, 20
students take computer science and mathematics, 20 take computer science and
physics, and 30 take mathematics and physics. We are interested in those
students that take courses in all three areas. Do we have enough information?
Let C, M, and P stand for the sets of students that take computer science,
mathematics, and physics. So we are interested in the number
.
From the
information given we know that
. The reason for the inequality is that some students may not
be taking any courses in the three areas. The statistics also give us the
following information:
;
;
;
;
;
.
Applying the
inclusion-exclusion principle (1.7), we have

Therefore
. So we can say that at most 10 of the students polled take
courses in all three areas. We would get an exact answer if we knew that each
student in the survey took at least one course from one of the three areas.