# Cardinality of Set Union

Jump to navigation
Jump to search

## Contents

## 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:

\(\displaystyle \card {S_1 \cup S_2 \cup S_3}\) | \(=\) | \(\displaystyle \card {S_1} + \card {S_2} + \card {S_3}\) | |||||||||||

\(\displaystyle \) | \(\) | \(\, \displaystyle - \, \) | \(\displaystyle \card {S_1 \cap S_2} - \card {S_1 \cap S_3} - \card {S_2 \cap S_3}\) | ||||||||||

\(\displaystyle \) | \(\) | \(\, \displaystyle + \, \) | \(\displaystyle \card {S_1 \cap S_2 \cap S_3}\) |

### General Case

Let $S_1, S_2, \ldots$ be sets.

Then:

\(\displaystyle \card {\bigcup_{i \mathop = 1}^n S_i}\) | \(=\) | \(\displaystyle \sum_{i \mathop = 1}^n \card {S_i}\) | |||||||||||

\(\displaystyle \) | \(-\) | \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop \le n} \card {S_i \cap S_j}\) | |||||||||||

\(\displaystyle \) | \(+\) | \(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop < k \mathop \le n} \card {S_i \cap S_j \cap S_k}\) | |||||||||||

\(\displaystyle \) | \(\cdots\) | \(\displaystyle \) | |||||||||||

\(\displaystyle \) | \(+\) | \(\displaystyle \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:

- $\displaystyle \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:

\(\displaystyle \card {A_1}\) | \(=\) | \(\displaystyle 10\) | |||||||||||

\(\displaystyle \card {A_2}\) | \(=\) | \(\displaystyle 15\) | |||||||||||

\(\displaystyle \card {A_3}\) | \(=\) | \(\displaystyle 20\) | |||||||||||

\(\displaystyle \card {A_1 \cap A_2}\) | \(=\) | \(\displaystyle 8\) | |||||||||||

\(\displaystyle \card {A_2 \cap A_3}\) | \(=\) | \(\displaystyle 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.

## Sources

- 1975: T.S. Blyth:
*Set Theory and Abstract Algebra*... (previous) ... (next): $\S 1$. Sets; inclusion; intersection; union; complementation; number systems: Exercise $8$