3
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Did you prove that a subset of a finite set is finite? $\endgroup$
    – Asaf Karagila
    Jan 20, 2015 at 15:58
  • $\begingroup$ Yes, shall I add the proof at my post? @AsafKaragila $\endgroup$
    – evinda
    Jan 20, 2015 at 15:59
  • $\begingroup$ No need. It's just a consequence of this fact, since $\bigcap A\subseteq a$ for all $a\in A$. $\endgroup$
    – Asaf Karagila
    Jan 20, 2015 at 16:05
  • $\begingroup$ @AsafKaragila I added the proof. And how could we the fact that $\bigcap A \subseteq a$ for $a \in A$? $\endgroup$
    – evinda
    Jan 20, 2015 at 16:18
  • $\begingroup$ 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. $\endgroup$
    – Ragnar1204
    Feb 12, 2017 at 1:04

1 Answer 1

3
$\begingroup$

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]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.