# 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