[Math] The union of finite sets is a finite set

elementary-set-theory

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

Best Answer

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.

enter image description here

The following is the proof that you may be interested in.

enter image description here

[sorry for posting pictures, but I prefer typing in a LaTeX editor for its macros + \newcommands + autocompletion]

Related Question