Union of Finite Sets is Finite

From ProofWiki
Jump to navigation Jump to search


Let $S$ and $T$ be finite sets.

Then $S \cup T$ is a finite set.

Proof 1

If $S$ or $T$ is empty, the result is trivial.

Otherwise, let $f: \N_{<n} \to S$ and $g: \N_{<m} \to T$ be bijections, where $\N_{<n}$ is an initial segment of $\N$.

Now define $h: \N_{< n + m} \to S \cup T$ by:

$\map h i = \begin{cases} \map f i : & \text {if $i < n$} \\ \map g {i - n} : & \text{if $i \ge n$} \end{cases}$

By Set Finite iff Surjection from Initial Segment of Natural Numbers, it suffices to show that $h$ is surjective.

Let $s \in S$.


\(\ds \map h {\map {f^{-1} } s}\) \(=\) \(\ds \map f {\map {f^{-1} } s}\) as $\map {f^{-1} } s \in \N_{<n}$
\(\ds \) \(=\) \(\ds s\) Definition of $f^{-1}$

Next let $t \in T$.

We have that:

$n + \map {g^{-1} } t < n + m$

so that:

$n + \map {g^{-1} } t \in \N_{< n + m}$


\(\ds \map h { n + \map {g^{-1} } t}\) \(=\) \(\ds \map g {n + \map {g^{-1} } t - n}\) as $\map {g^{-1} } t \ge 0$ and so $n + \map {g^{-1} } t \ge n$
\(\ds \) \(=\) \(\ds \map g {\map {g^{-1} } t}\)
\(\ds \) \(=\) \(\ds t\) Definition of $g^{-1}$

Thus it has been shown that for all $s \in S$ and $t \in T$, there exists an element of $\N_{< n + m}$ which maps to it.

So by definition of set union, for all $x \in S \cup T$:

$\exists y \in \N_{< n + m}: \map h y = x$.

Hence, by definition, $h$ is a surjection.

Therefore $S \cup T$ is finite.


Proof 2

Note that $\card {S \cup T} \le \card {S \times T}$ by Cardinal of Union Less than Cardinal of Cartesian Product.

The theorem follows from the fact that $S \times T$ is finite by Product of Finite Sets is Finite.