38 CHAPTER 1 Sets, Proof Templates, and Induction
The decomposition of two sets into disjoint subsets is fairly obvious. For three or more
sets, however, this is not as obvious a step. Figure 1.14 will help you to understand the next
theorem if you identify each of the regions of A U B U C.The sets of interest are identified as A, B, C, A n B, A n C, B n C, and A n B n C.
Theorem 3. (Principle of Inclusion-Exclusion for Three Sets) Let A, B, and C be
finite sets. Then,IAUBUCI = IAI+IBI+ICI-+AnBI-IAAnCI-lBnCI+IAAnBfnCI
Proof. The same style of proof as used in Theorem 2 could be used, but in this case, there
would be seven pieces to keep track of instead of three. A clearer way to proceed is to use
Theorem 2 in Section 1.5.2.A U B U C = I (A U B) U C I (by the definition of the union of three sets)
= IA U B I + I C I - I (A U B) n C I (by Theorem 2 in Section 1.5.2)
= I A U B + I C I - I (A n C) U (B n C) I (by Distributive Law for Intersection)= I A U B + I C I - (I A n C I + I B n C I - I (A n C) n (B n C) I) (by Theorem 2
in Section 1.5.2 on (A n C) U (B n C))
= I A U B I + I C I - I A n C - B CI + I(A n C) n (B A C)I
(removing parentheses)
=IAUBI+ICI-IAnCI-IBnCI+IAnBACI(simplifying I(A n C) n (B n C)I)
=IAI+IBI-IAnBI÷ICI-IAnCI-IBnCI+IAnBnCI
(by Theorem 2 in Section 1.5.2 again)
=IAI+IBI+ICI-IAnBI-IAnCI-IBnCI+IAnBnCIWhen the Principle of Inclusion-Exclusion is applied in the next example, the solution
becomes straightforward.Example 7. A particular political campaign mailing is expected to appeal to three groups
of people: liberals, people earning more than $45,000 a year, and people with children un-
der five years of age. The mailing list includes 30,000 people, including 15,000 conserva-
tives and 15,000 liberals. Of the 30,000 on the mailing list, 17,500 earn more than $45,000
a year, including 10,001 of the liberals. In the set of people, 3500 have children under five
years of age, including 1000 conservatives, 2500 liberals, and 900 of those who earn more
than $45,000 a year. Only one of the liberals earns more than $45,000 a year and also has
children under the age of five. How many people on the mailing list are liberals, or earn
more than $45,000 a year, or have children under five years of age? (As usual, by or we
mean the inclusive or.)Solution. Among people on the mailing list, let L be the set of liberals, E the set of
people who earn more than $45,000 a year, and C the set of people who have children
under five years of age (see Figure 1.15).