# Cardinality of Set Union/General Case

## Theorem

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

Then:

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

## Proof

By Cardinality is Additive Function, we can apply the Inclusion-Exclusion Principle:

If $f: \mathcal S \to \R$ is an additive function, then:

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

$\blacksquare$