Finite Union of Finite Sets is Finite

From ProofWiki
Jump to navigation Jump to search


Let $S$ be a finite set of finite sets.

Then the union of $S$ is finite.

Proof 1

The proof proceeds by induction.

Let $S$ be a finite set with cardinality $n$.

If $n = 0$ then $S = \O$, so $\bigcup S = \O$, which is finite.

Suppose that the union of any finite set of finite sets with cardinality $n$ has a finite union.

Let $S$ have cardinality $n^+$.

Then there is a bijection $f: n^+ \to S$.


$\ds \bigcup S = \bigcup_{k \mathop \in n^+} \map f k = \bigcup_{k \mathop \in n} \map f k \cup \map f n$

By Union of Finite Sets is Finite, $\bigcup S$ is finite.


Proof 2

Let $S = \set {A_1, \ldots, A_n}$ such that $A_k$ is finite $\forall k = 1, \ldots, n$.


$m = \max \set {\card {A_1}, \ldots, \card {A_n} }$


$\ds \card {\bigcup_{k \mathop = 1}^n A_k} \le \sum_{k \mathop = 1}^n \card {A_k} \le \sum_{k \mathop = 1}^n m = n m$

Hence the result.