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

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Finite Set
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Physics news on Phys.org
Once you know that the union of two finite sets is finite, you could use induction on the number of sets in $A$.
 
Evgeny.Makarov said:
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.}$$
 
Yes, that's fine.
 
Evgeny.Makarov said:
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?
 
evinda said:
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.

evinda said:
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.

evinda said:
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$.
 
Evgeny.Makarov said:
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$.

Evgeny.Makarov said:
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? :confused:

Evgeny.Makarov said:
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$$
 
Back
Top