Cardinality of Set Union/General Case

From ProofWiki
Jump to navigation Jump to search

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$


Sources