Cardinality of Set Union

Theorem

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

Then:

$\left|{S_1 \cup S_2}\right| = \left|{S_1}\right| + \left|{S_2}\right| - \left|{S_1 \cap S_2}\right|$

Also:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left\vert{S_1 \cup S_2 \cup S_3}\right\vert\)	\(=\)	\(\displaystyle \left\vert{S_1}\right\vert + \left\vert{S_2}\right\vert + \left\vert{S_3}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(-\)	\(\displaystyle \left\vert{S_1 \cap S_2}\right\vert - \left\vert{S_1 \cap S_3}\right\vert - \left\vert{S_2 \cap S_3}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(+\)	\(\displaystyle \left\vert{S_1 \cap S_2 \cap S_3}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

and in general:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left\vert{\bigcup_{i \mathop = 1}^n S_i}\right\vert\)	\(=\)	\(\displaystyle \sum_{i \mathop = 1}^n \left\vert{S_i}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(-\)	\(\displaystyle \sum_{1 \mathop \le i \mathop < j \le n} \left\vert{S_i \cap S_j}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(+\)	\(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop < k \mathop \le n} \left\vert{S_i \cap S_j \cap S_k}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\cdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(+\)	\(\displaystyle \left({-1}\right)^{n-1} \left\vert{\bigcap_{i \mathop = 1}^n S_i}\right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Corollary

Let $\mathcal S$ be an algebra of sets.

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

Then:

$\displaystyle \left\vert{\bigcup_{i \mathop = 1}^n S_i}\right\vert = \sum_{i \mathop = 1}^n \left\vert{S_i}\right\vert$

Proof

From the fact that Cardinality is an Additive Function, we can directly apply the Inclusion-Exclusion Principle:

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

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle f \left({\bigcup_{i \mathop = 1}^n S_i}\right)\)	\(=\)	\(\displaystyle \sum_{i \mathop = 1}^n f \left({S_i}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(-\)	\(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop \le n} f \left({S_i \cap S_j}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(+\)	\(\displaystyle \sum_{1 \mathop \le i \mathop < j \mathop < k \le n} f \left({S_i \cap S_j \cap S_k}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\cdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(+\)	\(\displaystyle \left({-1}\right)^{n-1} f \left({\bigcap_{i \mathop = 1}^n S_i}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

$\blacksquare$

Proof of Corollary

As $S_1, S_2, \ldots, S_n$ are pairwise disjoint, their intersections are all empty.

The main result holds, but from Cardinality of Empty Set, all the terms apart from the first vanish.

$\blacksquare$

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 13$: Arithmetic
• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 1.4$: Example $16$
• J.A. Green: Sets and Groups (1965)... (previous)... (next): Exercise $1.4$
• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $19.1$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 15 \beta$
• T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 1$: Exercise $8$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): Exercise $1.8$