TransWikia.com

Union of two non empty and mutually exclusive finite sets is finite

Mathematics Asked on December 27, 2021

Let $A$ and $B$ be two non empty finite sets. Also, $A cap B = varnothing$. Then I have to prove that $A cup B $ is a finite set. Following is my attempt. Since $A,B$ are finite sets, we have that $A thicksim I_m $ and $ B thicksim I_n $ for some $m,n in mathbb{N}$. Here following definitions are used,

$$ I_m = { iin mathbb{Z}^+ vert , i leqslant m } $$
$$ I_n = { iin mathbb{Z}^+ vert , i leqslant n } $$

This means that there is a bijection from $A$ to $I_m$ and there is a bijection from $B$ to $I_n$. Let the bijections be

$$ f_1 : A to I_m $$
$$ f_2 : B to I_n $$

I need to prove that $A cup B $ is a finite set. So, I need to prove that there is a bijection from $Acup B$ to $I_{m+n}$. Let me define a function.

$$ g :A cup Bto I_{m+n} $$

as follows.

$$ bbox[yellow] {g(x) = begin{cases}
f_1(x) & text{if $x in A$} \[2ex]
m + f_2(x) & text{if $x in B$}
end{cases} }
$$

Now, I will need to prove that this is a bijection. Consider $g(x_1) = g(x_2)$. Now, let me consider first case here.

Case 1) $x_1 in A$ and $x_2 in B$

In this case, using the definition, we have $f_1(x_1) = m + f_2(x_2) $. Now, since $f_1(x_1) subseteq I_m $, we have $ 1 leqslant f_1(x_1) leqslant m $. We also have $f_2(x_2) subseteq I_n $, so we get $ 1 leqslant f_2(x_2) leqslant n $. So we have,

$$ f_1(x_1) leqslant m < m+1 leqslant m + f_2(x_2) = f_1(x_1) $$

This leads to the contradiction $ f_1(x_1) < f_1(x_1) $. So, this case is not possible.

Case 2) $x_1 in A$ and $ x_2 in A$

This leads to $f_1(x_1) = f_1(x_2)$ , but $f_1$ is a bijection, so we have, $x_1 = x_2$

Case 3) $x_1 in B$ and $ x_2 in B$

This leads to $ m + f_2(x_1) = m + f_2(x_2) $ and since $f_2$ is a bijection, we have $ x_1 = x_2 $

So, in any case, $g(x_1) = g(x_2)$ leads to $x_1 = x_2$. This proves that $g(x)$ is a one-to-one function.

Now let $y in I_{m+n}$ be an arbitrary element in the $ I_{m+n}$. Here, we have two cases.

Case 1) $1 leqslant y leqslant m$

So, $y in I_m $ and since $f_1$ is an onto function, $exists , x in A$ such that $f_1(x) = y $. Since
$x in A$, we have $x in A cup B $ , so we can say, $g(x) = y$

Case 2) $ m+1 leqslant y leqslant m+n $

We have $ 1 leqslant y-m leqslant n $, so $ y-m in I_n$ and since $f_2$ is an onto function, $exists , x in B$ such that $f_2(x) = y-m $. So, $ m + f_2(x) = y $. Since $x in A$, we have $x in A cup B $. So, we have $ g(x) = y $.
So, in any case, we proved that $g(x)$ is an onto function. This means that $ g(x) $ is a bijection and $ A cup B thicksim I_{m+n} $. This proves that $ Acup B $ is a finite set.

If either $A = varnothing $ or $ B = varnothing $, then $ A cup B $ is equal to $A, B $ or $varnothing$. And since $varnothing$ is a finite set since $ varnothing thicksim I_0 $. So, $A cup B$ is a finite set even if either of $A$ or $B$ is an empty set. So, we need not restrict the statement to non empty sets.

So, does this sound correct ?

Thanks

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP