# The union of finite sets is a finite set

The union of two finite sets is a finite set.

Let $X,Y$ be finite sets.

That means that there are $n, m\in \omega$ such that $X \sim n$ and $Y \sim m$, i.e. there are functions $f: X \overset{\text{bijective}}{\rightarrow} n$, $g: Y \overset{\text{bijective}}{\rightarrow} m$.

Then we distinguish the cases: $X \bigcap Y=\varnothing$ and $X \bigcap Y \neq \varnothing$.

First case: $X \cap Y=\varnothing$

We define the function $h: X \cup Y \to m+l$

so that $h(x)=f(x)$ if $x \in X$, $h(y)=n+g(y)$ if $y \in Y$.

We want to show that $h: X \cup Y \overset{1-1}{\to} n+m$

Let $a,b \in X \cup Y$ with $h(a)=h(b)$

• if $a,b \in X$ then $h(a)=f(a)$ and $h(b)=f(b)$. Thus $f(a)=f(b) \Rightarrow a=b$ since $f$ is injective 
• if $a,b \in Y$ then $h(a)=m+g(a)$ and $h(b)=m+g(b)$. Thus $m+g(a)=m+g(b) \Rightarrow g(a)=g(b) \Rightarrow a=b$ since $g$ is injective 
• if $a \in X, b \in Y$ then $h(a)=f(a)<m$ and $h(b)=m+g(b) \geq m$, so in this case it cannot be that $h(a)=h(b)$

Then we show that $h: X \cup Y \to n+m$ is surjective.

In order to do this, we need to show that $\forall k \in n+m$ there is a $b \in X \cup Y$ such that $h(b)=k$.

So it suffices to show that $\forall k<n$ there is a $x \in X$ such that $h(x)=k$ and $\forall n \leq k<n+m$ there is a $y \in Y$ such that $h(y)=k$.

For $x \in X$: $h(x)=k \Rightarrow f(x)=k$ and we know that $\forall k<n, \exists x \in X$ such that $f(x)=k$ since $f$ is surjective.

For $y \in Y: h(y)=k \Rightarrow n+g(y)=k$

How can we continue, knowing that the subtraction between natural numbers is not defined?

Second case: $X \cup Y=(X-Y) \cup Y$ with $X-Y$ finite set , $Y$ finite set and $(X-Y) \cap Y=\varnothing$ so we reduce the problem to the first case.

Also, how could we show that if $A$ is a finite set of finite sets then $\bigcap A$ is finite?

The fact that $A$ is finite means that there is a natural number $n \in \omega$ such that $A \sim n$, i.e. there is a function $f: A \to n$ that is bijective.

But what bijective function could we pick in this case in order to prove that $\bigcap A$ is finite?

EDIT: The subsets of finite sets are finite sets.

We consider a finite set $A$. That means that there is a natural number $n \in \omega$ such that $A \sim n$, i.e. there is a bijective function $f: A \to n$.

Now we consider a subset $B$ of $A$.

Then $f|_B: B \overset{\text{bijective}}{\to} f(B)$

So it suffices to show that $f(B) \sim m, m \in \omega$.

$$B \subset A \rightarrow f(B) \subset f(A)=n \rightarrow f(B) \subset n$$

• $f(B)=n$ then we are done.

• $f(B) \subsetneq n$

If $B=\varnothing$ we have the trivial bijection $g: B \to 0$

Now we suppose that $B \neq \varnothing$.

We define a function $h: m \to f(B)$ such that $0 \mapsto \min{f(B)}\\k+1 \mapsto \min\{u \in f(B): u> h(k)\}$

It holds that $h(k)<n$. We will show that $h(k) \geq k$.

For $k=0: h(0)= \min{f(B)}=\varnothing=0 \geq 0 \checkmark$

We suppose that $h(k) \geq k$.

$$h(k+1)=\min{u \in f(B):u>h(k)}>k \geq k+1$$

Thus $k \leq h(k)< n \Rightarrow k<n$ and therefore $m \leq n$.

• Did you prove that a subset of a finite set is finite? Jan 20, 2015 at 15:58
• Yes, shall I add the proof at my post? @AsafKaragila Jan 20, 2015 at 15:59
• No need. It's just a consequence of this fact, since $\bigcap A\subseteq a$ for all $a\in A$. Jan 20, 2015 at 16:05
• @AsafKaragila I added the proof. And how could we the fact that $\bigcap A \subseteq a$ for $a \in A$? Jan 20, 2015 at 16:18
• Maybe, you can use this... If $k\in\{n+1,n+2,\ldots,n+m\}$; $k$ has the form $k=n+j$ with $j\in\{1,2,\ldots,m\}$ and there is a $y\in Y$ such that $g(y)=j$ then $n+g(y)=n+j=k$ and you can conclude that $h(y)=k$. So, $h$ is surjective. Feb 12, 2017 at 1:04

Halmos' Naive Set Theory gives a hint which is the following Lemma. It took me awhile to understand the hint's usefulness for proving that the union of two finite sets is finite. The following is the proof that you may be interested in. [sorry for posting pictures, but I prefer typing in a LaTeX editor for its macros + \newcommands + autocompletion]