Show $\bigcup A$ is Finite When $A$ is a Finite Set of Finite Sets

[evinda]

Hello! (Wave)

I want to show that if $A$ is a finite set of finite sets then the set $\bigcup A$ is finite.

The set $A$ is finite. That means that there is a natural number $n \in \omega$ such that $A \sim n$, i.e. there is a bijective function $f$ such that $f: A \overset{\text{bijective}}{\rightarrow} n$.

If we would want to show that $B \cup C$, $B, C \in A$ is a finite set we would do the following:

$A,B$ are finite sets. That means that there are $m, l \in \omega$ such that $A \sim m$ and $B \sim l$, i.e. there are functions $f: A \overset{\text{bijective}}{\rightarrow} m$, $g: B \overset{\text{bijective}}{\rightarrow} l$.

Then we distinguish the cases: $A \bigcap B=\varnothing$ and $A \bigcap B \neq \varnothing$.First case: $A \cap B=\varnothing$

We define the function $h: A \cup B \to m+l$

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

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

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.

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.

What can we do now that we consider more that two finite sets? What function could we pick? (Thinking)

 

[Evgeny.Makarov]

Once you know that the union of two finite sets is finite, you could use induction on the number of sets in $A$.

 

[evinda]

Once you know that the union of two finite sets is finite, you could use induction on the number of sets in $A$.

So could we do it like that? (Thinking)

• The union of two finite sets is a finite set.
• Suppose that the union of $k$ finite sets is a finite set.
• We will show that the union of $k+1$ finite sets is a finite set.
  Suppose that we have the following finite sets: $A_1, A_2, \dots, A_{k+1}$
  
  $$A_1 \cup A_2 \cup \dots A_k \cup A_{k+1}=(A_1 \cup A_2) \cup A_3 \dots A_k \cup A_{k+1} \overset{\star}{=} C_1 \cup A_3 \dots A_k \cup A_{k+1} $$
  
  We see that $C_1 \cup A_3 \dots A_k \cup A_{k+1}$ is a union of $k$ finite sets, so from the induction hypothesis we have that $A_1 \cup A_2 \cup \dots A_k \cup A_{k+1}$ is a finite set.$$\star: \text{ We set } C_1=A_1 \cup A_2 \text{ which is a finite set from the base-case.}$$

 

[Evgeny.Makarov]

Yes, that's fine.

 

[evinda]

Yes, that's fine.

Great! Thanks a lot! (Happy)Could I also ask you something about the proof that the union of two finite sets is a finite set?

We want to 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?

 

[Evgeny.Makarov]

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

Don't you have a theorem that $A$ is finite iff there is an injection from $A$ to some natural number $n$? Once this is proved, there is no need to prove surjectivity.

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.

I am not sure I understand the logic here. What you have is $k<n$; there is no $x$ given.

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?

You can prove the property that if $n \leq k<n+m$ and $n+i=k$, then $0\le i<m$.

 

[evinda]

Don't you have a theorem that $A$ is finite iff there is an injection from $A$ to some natural number $n$? Once this is proved, there is no need to prove surjectivity.

No (Shake) According to my notes, $A$ is finite iff there is a bijection from $A$ to some natural number $n$.

I am not sure I understand the logic here. What you have is $k<n$; there is no $x$ given.

So we have to start from $k<n$, right? But what could we say about that?

You can prove the property that if $n \leq k<n+m$ and $n+i=k$, then $0\le i<m$.

Could we prove the property using induction on [m] n [/m] as follows?

• For $n=0: 0 \leq k <m \wedge n=k \rightarrow 0 \leq i<m \checkmark$
• Suppose that for some $n \in \omega$ and $\forall m, i \in \omega$ it holds that: $n \leq k < n+m \wedge n+i=k \rightarrow 0 \leq i<m$
• We will show that $n+1 \leq k<n+1+m \wedge n+1+i=k \rightarrow 0 \leq i<m$
  
  $n+1 \leq k<n+1+m \rightarrow n+1+i \leq k+i<n+1+m+i \rightarrow k \leq k+i < k+m \rightarrow \overset{\star}{\to} 0 \leq i<m$

$$\star: \text{ From the induction hypothesis, we have: } \\ n \leq k< n+m \wedge n+i=k \rightarrow 0 \leq i <m \Leftrightarrow n+i \leq k+i< n+m+i \wedge n+i=k \\ \rightarrow k \leq k+i<k+m$$