Let $A$ and $B$ be two disjoint sets which are finite. I am proving that $A\cup B$ is also finite. If either $A$ or $B$ is an empty set $\varnothing$, then $A \cup B$ is either $A$ or $B$. And so $A\cup B$ is a finite set. So, we will assume that $A \ne \varnothing$ and $B \ne \varnothing$. Since $A$ and $B$ are finite sets, there are bijections $f : A \to I_m$ and $g : B \to I_n$. Where, $I_m = \{ i \in \mathbb{Z}^+ \, |\, i \leq m \} $ and $I_n = \{ i \in \mathbb{Z}^+ \, | \,i \leq n \} $. Now, I need to prove that $A\cup B$ is also finite. So, I need to come up a bijection from $A\cup B$ to $I_{m+n}$. Now, consider the following binary relation $h$ from $A\cup B$ to $I_{m+n}$.
$$ (x, f(x)) \in h \, \text{ if } x \in A \\
(x, m + g(x)) \in h \, \text{ if } x \in B $$
Now, I will prove that this is a function. Let $x \in A \cup B$ be arbitrary. Since they are disjoint, this means that we have two cases. If $x \in A$, we have some $1 \leqslant k_1 \leqslant m$ in $I_m$ such that $f(x) = k_1$. And , if $x \in B$, we have some $1 \leqslant k_2 \leqslant n$ in $I_n$ such that $g(x) = k_2$. So, $m + g(x) = m + k_2$. Now, we have $ k_1 \in I_{m+n}$ and $m + k_2 \in I_{m+n}$. So, it follows that if $x \in A$, then $(x , k_1) \in h$ and if $x \in B$, then $m + k_2 \in h$. So, we proved the existence of some element $y$ in $I_{m+n}$ such that $(x,y) \in h$. Now, suppose there are two such elements $y_1$ and $y_2$. So, we have $(x,y_1) \in h$ and $(x,y_2) \in h$. Now, here if $x \in A$, then $y_1 = f(x)$ and $y_2 = f(x)$. It follows that $y_1 = y_2$. If, $x \in B$, then $y_1 = m + g(x)$ and $y_2 = m + g(x)$. Again, it follows that $y_1 = y_2$. So, now we proved the uniqueness. So, this proves that $h$ is a function. So, we have
$$ h: A\cup B \to I_{m+n} $$
$$ h(x) =
\begin{cases}
f(x) & \text{if $x \in A$} \\
m + g(x) & \text{if $x \in B$}
\end{cases}
$$
Now, the task is to prove that this function is a bijection. Consider $h(x_1) = h(x_2)$. Now, there are three cases to consider.
Case 1) $x_1, x_2 \in A$
In this case, we have $f(x_1) = f(x_2)$ and since $f$ is a bijection, we have $x_1 = x_2$.
Case 2) $x_1 \in A$ and $x_2 \in B$
In this case, $f(x_1) = m + g(x_2)$. But $1 \leqslant f(x_1) \leqslant m$ and $1 \leqslant g(x_2) \leqslant n$. It follows that $m < m + 1 \leqslant m + g(x_2) \leqslant m+n$. This means that $f(x_1) \leqslant m < m + g(x_2) = f(x_1)$. This is $f(x_1) < f(x_1)$. This is a contradiction. So, this case is never possible.
Case 3) $x_1, x_2 \in B$
Here, we have $m + g(x_1) = m + g(x_2)$. Cancelling $m$ and noting that $g$ is a bijection, we get that $x_1 = x_2$.
So, it is proven that $h: A\cup B \to I_{m+n}$ is a one to one function. Now, we will prove that its also an onto function.
Let $k \in I_{m+n}$ be some arbitrary element. $ 1 \leqslant k \leqslant m+n $. We will consider two cases here.
Case 1) $ 1 \leqslant k \leqslant m $
Here $k \in I_m$. Since $f$ is an onto function, we have some $x \in A$ such that $f(x) = k$. So, we have $f(x) \in I_{m+n}$ and $ x \in A \cup B$. Using the definition of function $h$, we have $h(x) = f(x) = k$. So, there is some element $x \in A \cup B$ such that $h(x) = k$.
Case 2) $m + 1 \leqslant k \leqslant m+n$
It follows that $ 1 \leqslant k-m \leqslant n$. So, $ k-m \in I_n$ and since function $g$ is an onto function, there is some $x \in B$ such that $g(x) = k-m $. So, $ m + g(x) = k $. Since $ k \in I_{m+n}$ , we have $ m + g(x) \in I_{m+n}$ and since $x \in B$, we have $x \in A \cup B$. So using the definition of function $h$, we have $h(x) = k$.
So, in both cases, it follows that there is some element $y$ in $A\cup B$ such that $h(x) = y$. Which means that function $h: A\cup B \to I_{m+n}$ is an onto function.
This means that the function $h: A\cup B \to I_{m+n}$ is a bijection. We have $ A\cup B \thicksim I_{m+n}$ and so $A \cup B$ is a finite set.
Is this a good proof ?
Thanks
Best Answer
If there are bijections $f:A\to [1,n]$ and $g:B\to [1,m]$, there is a bijection $g':B\to[n+1,n+m]$.
Then there is a function $h:A\cup B\to [1,n+m]$ by the natural mapping of the elements of $A$ and $B\setminus A$ to their images by the respective bijections $f$ and $g'$.
From this function $h$ you can define a finite bijection $h'$ by dropping the naturals with no preimage. (Hence disjointness is not even required.)
This was the long way to say
$$\#(A\cup B)\le\#A+\#B.$$
It does not take much to improve the result as
$$\#(A\cup B)+\#(A\cap B)=\#A+\#B.$$