Prove that cardinality of union of $2$ finite sets is less than or equal to the sum of their cardinality.

So, here's what I thought of doing: $X$ and $Y$ are the 2 finite sets, with #$X=n$ and #$Y=m$ where # is cardinality.

To prove: #$(X\cup Y) \leq$ #$X+$#$Y$

I defined a function $h:X\cup(Y\setminus X)\rightarrow\{1,2...,n+m-k\}$ as \begin{equation*} h(x)=\begin{cases} f(x) \quad &\text{if} \, x \in X \\ g(x)+n \quad &\text{if} \, x \in Y\setminus X \\ \end{cases} \end{equation*} Where $f:X\rightarrow\{1,2...,n\}$ is a bijection and $g:(Y\setminus X)\rightarrow\{1,2...,m-k\}$ is another bijection, and $k=$#$(Y\cap X)$. $f$ is a bijection because of the finite set $X$ with cardinality $n$. But I want to prove that $h$ is a bijection, for which I will need to prove that $g$ is a bijection as well. I am having a hard time figuring out how to prove that $g$ is a bijection. Any help is appreciated.

Solution 1:

From what you say about the existence of the bijection $f \colon X \to \{1, 2, \ldots, n\}$, it seems like you already know that a finite set $X$ has cardinality $n$ if and only if there exists a bijection between $X$ and $\{1, 2, \ldots, n\}.$

We will use this fact to prove the following lemma:

Lemma: If $A$ and $B$ are disjoint finite sets, $\#(A \cup B) = \#A + \#B.$

Proof: Let $\#A = a$ and $\#B = b.$ There exist bijections $f_{1} \colon A \to \{1, 2, \ldots, a\}$ and $g_{1} \colon B \to \{1, 2, \ldots, b\}.$ Define $h_{1} \colon A \cup B \to \{1, 2, \ldots, a+b\}$ by $$h_{1}(x) = \begin{cases} f_{1}(x) & x \in A \\ g_{1}(x) + a & x \in B. \end{cases}$$ Since $A$ and $B$ are disjoint, $h_{1}(x)$ is well defined.

Let $x, y \in A \cup B$ be two distinct elements. If $x, y \in A,$ then $h_{1}(x) = f_{1}(x) \neq f_{1}(y) = h_{1}(y)$ because $f_{1}$ is a bijection. By the same reasoning, if $x, y \in B,$ then $h_{1}(x) \neq h_{1}(y)$. Finally, if $x \in A$ and $y \in B$ (the case where $x \in B$ and $y \in A$ is exactly the same), then $h_{1}(x) \leq a < h_{1}(y),$ so $h_{1}(x) \neq h_{1}(y)$ as well. Therefore, $h_{1}$ is injective.

Now, let $c \in \{1, 2, \ldots, a+b\}$ be arbitrary. If $c \in \{1, 2, \ldots, a\},$ then by surjectivity of $f_{1}$ there exists $x \in A$ such that $f_{1}(x) = c,$ and so $h_{1}(x) = f_{1}(x) = c$ as well. If $c \in \{a+1, a+2, \ldots, a+b\},$ then $c- a \in \{1, 2, \ldots, b\}.$ By surjectivity of $g_{1}$ there exists $x \in B$ such that $g_{1}(x) = c-a,$ and so $h_{1}(x) = g_{1}(x) + a = c$. Since these are the only two possible cases for $c,$ we conclude that $h_{1}$ is injective.

So, $h_{1}$ is a bijection between $A \cup B$ and $\{1, 2, \ldots, a+b\}$, hence $$\#(A \cup B) = a+b = \#A + \#B.$$ $$\hspace{15cm} \blacksquare$$

Returning to the original problem, note that $Y \cap X$ and $Y \setminus X$ are disjoint, and that $(Y \cap X) \cup (Y \setminus X) = Y.$ So, using our lemma, we have $$\#Y = \#(Y \cap X) + \#(Y \setminus X).$$ However, since $\#Y = m$ and $\#(Y \cap X) = k,$ we conclude that $\#(Y \setminus X) = m - k.$ It follows that there is a bijection $g \colon Y \setminus X \to \{1, 2, \ldots, m-k\}$, as desired.

The rest of the proof should follow very similarly to the proof of the lemma.