Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 1] SET THEORY 9

Proof.In counting the elements ofA∪B, first count those that are inA. There aren(A)of these. The only other
elements ofA∪Bare those that are inBbut not inA. But sinceAandBare disjoint, no element ofBis inA,
so there aren(B)elements that are inBbut not inA. Therefore,n(A∪B)=n(A)+n(B).
For any setsAandB, the setAis the disjoint union ofA\BandA∩B. Thus Lemma 1.6 gives us the
following useful result.

Corollary 1.7: LetAandBbe finite sets. Then

n(A\B)=n(A)−n(A∩B)

For example, suppose an art classAhas 25 students and 10 of them are taking a biology classB. Then the number
of students in classAwhich are not in classBis:

n(A\B)=n(A)−n(A∩B)= 25 − 10 = 15

Given any setA, recall that the universal setUisthe disjoint union ofAandAC. Accordingly, Lemma 1.6
also gives the following result.

Corollary 1.8: LetAbe a subset of a finite universal setU. Then

n(AC)=n(U)−n(A)

For example, suppose a classUwith 30 students has 18 full-time students. Then there are 30− 18 =12 part-time
students in the classU.

Inclusion–Exclusion Principle

There is a formula forn(A∪B)even when they are not disjoint, called the Inclusion–Exclusion Principle.
Namely:

Theorem (Inclusion–Exclusion Principle) 1.9: SupposeAandBare finite sets. ThenA∪BandA∩Bare
finite and
n(A∪B)=n(A)+n(B)−n(A∩B)

That is, we find the number of elements inAorB(or both) by first addingn(A)andn(B)(inclusion) and then
subtractingn(A∩B)(exclusion) since its elements were counted twice.
We can apply this result to obtain a similar formula for three sets:

Corollary 1.10: SupposeA,B,Care finite sets. ThenA∪B∪Cis finite and

n(A∪B∪C)=n(A)+n(B)+n(C)−n(A∩B)−n(A∩C)−n(B∩C)+n(A∩B∩C)

Mathematicalinduction(Section 1.8) may be used to further generalize this result to any number of finite sets.

EXAMPLE 1.8 Suppose a listAcontains the 30 students in a mathematics class, and a listBcontains the
35 students in an English class, and suppose there are 20 names on both lists. Find the number of students:
(a) only on listA, (b) only on listB, (c) on listAorB(or both), (d) on exactly one list.

(a) ListAhas 30 names and 20 are on listB; hence 30− 20 =10 names are only on listA.

(b) Similarly, 35− 20 =15 are only on listB.

(c) We seekn(A∪B). By inclusion–exclusion,

n(A∪B)=n(A)+n(B)−n(A∩B)= 30 + 35 − 20 = 45.

In other words, we combine the two lists and then cross out the 20 names which appear twice.

(d) By (a) and (b), 10+ 15 =25 names are only on one list; that is,n(A⊕B)=25.