9.3: Cardinality of a Union

We know that if $A$ and $B$ are disjoint, then the cardinality of $A \cup B$ is $\# A+\# B$. Here is a formula that works even when the sets are not disjoint:

Proposition $9.3.1$.

For any finite sets $A$ and $B$, we have

$$#(A \cup B)=\# A +\# B-\#(A \cap B).$$

Proof

From Exercise $4.5.6$, we know that $A \backslash B$, $B \backslash A$, and $A \cap B$ are pairwise-disjoint, and that their union is $A \cup B$, so $$\#(A \backslash B)+\#(B \backslash A)+\#(A \cap B)=\#((A \backslash B) \cup(B \backslash A) \cup(A \cap B))=\#(A \cup B) .$$

Also, we have $$\begin{aligned} \# A &=\#((A \backslash B) \cup(A \cap B)) \\ &=\#(A \backslash B)+\#(A \cap B) \end{aligned}$$

(First: Exercise $4.5.4(2)$ Second: Exercise $4.5.5(4)$).

Similarly, we have $$\# B=\#(B \backslash A)+\#(A \cap B).$$

Therefore $$\begin{aligned} \# A+\# B &=(\#(A \backslash B)+\#(A \cap B))+(\#(B \backslash A)+\#(A \cap B)) \\ &=\#(A \backslash B)+\#(B \backslash A)+2 \#(A \cap B) \\ &=\#(A \cup B)+\#(A \cap B) . \end{aligned}$$

The desired conclusion is obtained by subtracting $\#(A \cap B)$ from both sides.

Figure $9A$. The sum $\# A+\# B$ includes all the elements of $A \cup B$, but counts the elements of $A \cap B$ twice, so $\# A+\# B=\#(A \cup B)+\#(A \cap B)$. Therefore $\#(A \cup B)=\# A+\# B-\#(A \cap B)$.

Example $9.3.2$.

Let $A=\{\mathrm{p}, \mathrm{r}, \mathrm{o}, \mathrm{n}, \mathrm{g}\}$ and $B=\{\mathrm{h}, \mathrm{o}, \mathrm{r}, \mathrm{n}, \mathrm{s}\}$. Then

Solution

$$\# A=5, \# B=5, \text { and } \#(A \cap B)=\#\{\mathrm{r}, \mathrm{o}, \mathrm{n}\}=3,$$

so Proposition $9.3.1$ tells us that $$\#(A \cup B)=\# A+\# B-\#(A \cap B)=5+5-3=7 .$$

This is correct, since #(A ∪ B) = #{p,r, o, n, g, h,s} = 7.

Example $9.3.3$.

Every one of the 4000 students at Modern U owns either a cell phone or an iPod (or both). Surveys show that:

• 3500 students own a cell phone, and
• 1000 students own an iPod.

How many students own both a cell phone and an iPod?

Solution

Let

• $S$ be the set of all students at Modern U,
• $C$ be the set of students who own a cell phone, and
• $I$ be the set of students who own an iPod.

Then, by assumption, $$\# S=4000, \quad \# C=3500, \quad \# I=1000$$

Since every student owns either a cell phone or an iPod, we have $S=C \cup I$. Therefore, Proposition $9.3.1$ tells us that $$\# S=\#(C \cup I)=\# C+\# I-\#(C \cap I),$$

so $$\#(C \cap I)=\# C+\# I-\# S=3500+1000-4000=500 \text {. }$$

Hence, there are exactly 500 students who own both a cell phone and an iPod.

Exercise $9.3.4$.

1. Assume $\# U=15$, $\# V=12$, and $\# (U \cap V)=4$. Find $\# (U \cup V )$.
2. Assume $\# R=13$, $\# S=17$, and $\# (R \cup S)=25$. Find $\# (R \cap S)$.
3. Assume $\# J = 300$, $\# (J \cup L) = 500$, and $\# (J \cap L) = 150$. Find $\# L$.
4. At a small university, there are 90 students that are taking either Calculus or Linear Algebra (or both). If the Calculus class has 70 students, and the Linear Algebra class has 35 students, then how many students are taking both Calculus and Linear Algebra?
5. (harder) Suppose $A$, $B$, and $C$ are finite sets. Show $$\begin{aligned} \#(A \cup B \cup C)=\# A+\# B+\# C \\ -\#(A \cap B)-\#(A \cap C)-\#(B \cap C) \\ &+\#(A \cap B \cap C) . \end{aligned}$$
   [Hint: We have formulas for $\#((A \cup B) \cup C)$ and $\# (A \cup B)$. Another useful formula comes from the equality $(A \cup B) \cap C=(A \cap C) \cup(B \cap C) .]$.]

The following exercises are examples of another type of application of the formula for the cardinality of a union.

Exercise $9.3.5$.

1. Suppose $A$ and $B$ are subsets of a finite set $C$. Show that if $\# A+\# B>\# C$, then $A \cap B \neq \varnothing$. [Hint: Use Proposition $9.3.1$ to show that $\#(A \cap B) \neq 0$.]
2. Show that if $A$ is a set of at least 600 natural numbers that are less than 1000, then two of the numbers in $A$ differ by exactly 100. [Hint: Let $B=\{a+100 \mid a \in A\}$, and use the preceding exercise to show that $A \cap B \neq \varnothing$.]

Exercise $9.3.6$.

1. Suppose $A_{1}, A_{2}, \ldots, A_{n}$ are finite sets. Show $$\#\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right) \leq \# A_{1}+\# A_{2}+\cdots+\# A_{n} .$$
   [Hint: The induction step uses Proposition $9.3.1$.]
2. Prove the Pigeonhole Principle ($9.2.1$).
   [Hint: The contrapositive states that if $\# A_{i} \leq 1$ for every $i$, then $\#\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right) \leq n$.]

Remark $9.3.7$.

Generalizing Exercise $9.3.4(5)$, the Inclusion-Exclusion formula calculates the cardinality of the union of any number of sets: $$\left|A_{1} \cup \cdots \cup A_{n}\right|=\sum_{i=1}^{n}\left|A_{i}\right|-\sum_{1 \leq i<j \leq n}\left|A_{i} \cap A_{j}\right|+\sum_{1 \leq i<j<k \leq n}\left|A_{i} \cap A_{j} \cap A_{k}\right|-\cdots+(-1)^{n+1}\left|A_{1} \cap \cdots \cap A_{n}\right|.$$

(The sign +/− depends on the number of sets being intersected: odd intersections are added, and even intersections are subtracted, which agrees with both Proposition $9.3.1$ and Exercise $9.3.4(5)$.) We do not need this formula, but you can read about it in a Combinatorics textbook (or on Wikipedia).