# Cardinality of Set Union

## Theorem

### Union of 2 Sets

Let $S_1$ and $S_2$ be finite sets.

Then:

$\card {S_1 \cup S_2} = \card {S_1} + \card {S_2} - \card {S_1 \cap S_2}$

### Union of 3 Sets

Let $S_1$, $S_2$ and $S_3$ be finite sets.

Then:

 $\ds \card {S_1 \cup S_2 \cup S_3}$ $=$ $\ds \card {S_1} + \card {S_2} + \card {S_3}$ $\ds$  $\, \ds - \,$ $\ds \card {S_1 \cap S_2} - \card {S_1 \cap S_3} - \card {S_2 \cap S_3}$ $\ds$  $\, \ds + \,$ $\ds \card {S_1 \cap S_2 \cap S_3}$

### General Case

Let $\sequence {S_n}_{n \mathop \in \N}$ be a sequence of sets.

Then:

 $\ds \card {\bigcup_{i \mathop = 1}^n S_i}$ $=$ $\ds \sum_{i \mathop = 1}^n \card {S_i}$ $\ds$  $\, \ds - \,$ $\ds \sum_{1 \mathop \le i \mathop < j \mathop \le n} \card {S_i \cap S_j}$ $\ds$  $\, \ds + \,$ $\ds \sum_{1 \mathop \le i \mathop < j \mathop < k \mathop \le n} \card {S_i \cap S_j \cap S_k}$ $\ds$  $\ds \cdots$ $\ds$  $\, \ds + \,$ $\ds \paren {-1}^{n - 1} \card {\bigcap_{i \mathop = 1}^n S_i}$

### Corollary

Let $S_1, S_2, \ldots, S_n$ be finite sets which are pairwise disjoint.

Then:

$\ds \card {\bigcup_{i \mathop = 1}^n S_i} = \sum_{i \mathop = 1}^n \card {S_i}$

Specifically:

$\card {S_1 \cup S_2} = \card {S_1} + \card {S_2}$

## Examples

### Example: 3 Arbitrary Sets

Let $A_1, A_2, A_3$ be finite sets.

Let:

 $\ds \card {A_1}$ $=$ $\ds 10$ $\ds \card {A_2}$ $=$ $\ds 15$ $\ds \card {A_3}$ $=$ $\ds 20$ $\ds \card {A_1 \cap A_2}$ $=$ $\ds 8$ $\ds \card {A_2 \cap A_3}$ $=$ $\ds 9$

Then:

$26 \le \card {A_1 \cup A_2 \cup A_3} \le 28$

### Example: Examination Candidates

In a particular examination, there were $3$ questions.

All candidates attempted at least one of the questions.

$40$ candidates attempted question $1$.
$47$ candidates attempted question $2$.
$31$ candidates attempted question $3$.

Also, it was apparent that:

$9$ candidates attempted at least questions $1$ and $2$.
$15$ candidates attempted at least questions $1$ and $3$.
$11$ candidates attempted at least questions $2$ and $3$.

and:

exactly $6$ candidates attempted all $3$ questions.

It follows that $89$ candidates sat the examination in total.

### Example: Student Subjects

In a particular group of $75$ students, all studied at least one of the subjects mathematics, physics and chemistry.

All candidates attempted at least one of the questions.

$40$ students studied mathematics.
$60$ students studied physics.
$25$ students studied chemistry.

Also:

exactly $5$ students studied all $3$ subjects.

It follows that:

#### Mathematics and Physics

at least $25$ students studied both mathematics and physics.

#### Physics and Chemstry

at least $10$ students studied both physics and chemistry.

#### Mathematics and Chemistry

no more than $20$ students studied both mathematics and chemistry.