Counting elements: cardinal number results

How many stu­dents in a class play cricket or foot­ball, if we know how many play each and how many play both? Ques­tions like this are answered by a small set of results about car­di­nal num­bers. Each one comes from look­ing at the regions of a Venn dia­gram and count­ing every ele­ment exactly once. This les­son col­lects the results; the next two lessons use them to solve prob­lems.

The regions of a Venn dia­gram#

For two sets $A$ and $B$ in a uni­ver­sal set $U$, label the num­ber of ele­ments in each region:

Then $n(A) = a + b$, $n(B) = b + c$, $n(A \cup B) = a + b + c$, and $n(U) = a + b + c + d$. Every result below can be checked from these four num­bers.

Results for two sets#

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

Adding $n(A)$ and $n(B)$ counts the over­lap twice: $(a + b) + (b + c) = a + 2b + c$. Sub­tract­ing $n(A \cap B) = b$ once cor­rects this.

2. $n(A \cup B) = n(A) + n(B)$ when $A$ and $B$ are dis­joint, since then there is no over­lap.

3. $n(A - B) = n(A) - n(A \cap B) = n(A \cup B) - n(B) = n(A \cap B')$. Each of these equals $a$.

4. $n(B - A) = n(B) - n(A \cap B) = n(A \cup B) - n(A) = n(B \cap A')$. Each equals $c$.

5. $n(A \,\Delta\, B) = n(A - B) + n(B - A) = n(A) + n(B) - 2n(A \cap B) = n(A \cup B) - n(A \cap B)$. Each equals $a + c$.

6. $n(A') = n(U) - n(A)$, since $A' = U - A$.

7. $n(A' \cup B') = n\left((A \cap B)'\right) = n(U) - n(A \cap B)$, using De Mor­gan's law.

8. $n(A' \cap B') = n\left((A \cup B)'\right) = n(U) - n(A \cup B)$, also by De Mor­gan's law. This counts the ele­ments in nei­ther set.

Exam­ple 1#

If $n(U) = 700$, $n(A) = 200$, $n(B) = 300$ and $n(A \cap B) = 100$, find $n(A' \cap B')$.

$$\begin{aligned} n(A' \cap B') &= n\left((A \cup B)'\right) \\ &= n(U) - n(A \cup B) \\ &= n(U) - \left[n(A) + n(B) - n(A \cap B)\right] \\ &= 700 - (200 + 300 - 100) \\ &= 700 - 400 = 300 \end{aligned}$$

Exam­ple 2#

If $n(A) = 50$, $n(B) = 20$ and $n(A \cap B) = 10$, find $n(A \,\Delta\, B)$.

$$n(A \,\Delta\, B) = n(A - B) + n(B - A) = \left[n(A) - n(A \cap B)\right] + \left[n(B) - n(A \cap B)\right] = n(A) + n(B) - 2n(A \cap B)$$

So $n(A \,\Delta\, B) = 50 + 20 - 2 \times 10 = 50$.

How large can a union or inter­sec­tion be?#

9. $n(A \cap B) \le n(A)$ and $n(A \cap B) \le n(B)$, because $A \cap B$ is a sub­set of both. So $n(A \cap B)$ is at most the smaller of $n(A)$ and $n(B)$.

10. Let $n(A) = p$ and $n(B) = q$. Then:

The union is small­est when the smaller set lies inside the larger one, and largest when the sets are dis­joint. The inter­sec­tion is largest when one set lies inside the other, and small­est (0) when they are dis­joint. For instance, with $p = 2$ and $q = 3$:

Exam­ple 3#

Sets $A$ and $B$ have 3 and 6 ele­ments. What is the least num­ber of ele­ments in $A \cup B$? The great­est?

The least is $\max\{3, 6\} = 6$, when $A \subseteq B$. The great­est is $3 + 6 = 9$, when $A$ and $B$ are dis­joint.

Results for three sets#

11. $n(A \cup B \cup C) = n(A) + n(B) + n(C) - n(A \cap B) - n(B \cap C) - n(C \cap A) + n(A \cap B \cap C)$

Adding the three sets counts the pair­wise over­laps twice; sub­tract­ing the three pair­wise inter­sec­tions cor­rects that, but the cen­tral region $A \cap B \cap C$ has now been added three times and sub­tracted three times, so it is added back once.

Label the seven regions of the three-cir­cle dia­gram: $x_1$, $x_5$, $x_7$ for "only $A$", "only $B$", "only $C$"; $x_2$, $x_6$, $x_4$ for "$A$ and $B$ only", "$B$ and $C$ only", "$A$ and $C$ only"; and $x_3$ for the cen­tre, in all three.

12. Ele­ments in exactly one of the sets:

$$n(A) + n(B) + n(C) - 2\left[n(A \cap B) + n(B \cap C) + n(A \cap C)\right] + 3n(A \cap B \cap C)$$

Check with the regions: $n(A) + n(B) + n(C)$ counts each "only" region once, each "two only" region twice, and the cen­tre three times. Sub­tract­ing twice the pair­wise inter­sec­tions removes each "two only" region twice and the cen­tre six times. Adding $3x_3$ restores the cen­tre to zero. What is left is $x_1 + x_5 + x_7$.

13. Ele­ments in exactly two of the sets:

$$n(A \cap B) + n(B \cap C) + n(C \cap A) - 3n(A \cap B \cap C)$$

Each pair­wise inter­sec­tion is a "two only" region plus the cen­tre, so the three of them add up to the three "two only" regions plus three times the cen­tre.

Exam­ple 4#

Given $n(A) = 20$, $n(B) = 25$, $n(C) = 30$, $n(A \cap B) = 8$, $n(B \cap C) = 10$, $n(A \cap C) = 7$ and $n(A \cap B \cap C) = 3$, find $n(A \cup B \cup C)$ and the num­bers of ele­ments in exactly one and in exactly two of the sets.

$n(A \cup B \cup C) = 75 - 25 + 3 = 53$.

Exactly two: $25 - 3 \times 3 = 16$.

Exactly one: $75 - 2 \times 25 + 3 \times 3 = 34$.

Check: exactly one, exactly two and all three together give $34 + 16 + 3 = 53$, which is $n(A \cup B \cup C)$.

Prac­tice#

1. If $n(A) = 12$, $n(B) = 17$ and $n(A \cup B) = 21$, find $n(A \cap B)$.
2. If $A$ and $B$ are dis­joint, with $n(A) = 15$ and $n(B) = 10$, find $n(A \cup B)$.
3. If $n(U) = 50$, $n(A) = 20$, $n(B) = 25$ and $n(A \cap B) = 8$, find $n(A' \cap B')$ and $n(A' \cup B')$.
4. If $n(A) = 30$, $n(B) = 18$ and $n(A \cap B) = 6$, find $n(A - B)$, $n(B - A)$ and $n(A \,\Delta\, B)$.
5. If $n(A) = 8$ and $n(B) = 5$, find the least and great­est pos­si­ble val­ues of $n(A \cup B)$ and of $n(A \cap B)$.
6. If $n(A) = n(B) = n(C) = 10$, each pair­wise inter­sec­tion has 4 ele­ments and $n(A \cap B \cap C) = 2$, find $n(A \cup B \cup C)$.
7. For the sets in ques­tion 6, how many ele­ments are in exactly one set, and how many in exactly two?
8. If $n(U) = 40$ and $n(A) = 15$, find $n(A')$.
9. If $n(A \cup B) = 40$, $n(A) = 25$ and $n(B) = 22$, find $n(A \,\Delta\, B)$.
10. If $n(U) = 60$, $n(A') = 35$, $n(B') = 30$ and $n(A \cap B) = 10$, find $n\left((A \cup B)'\right)$.

Answers#