Union of Finite Sets is Finite/Proof 1

From ProofWiki
Jump to navigation Jump to search

Theorem

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


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


Proof

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$.

Then:

\(\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}$

Then:

\(\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.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Union_of_Finite_Sets_is_Finite/Proof_1&oldid=738171"