cardinality of disjoint union of finite sets

To begin we will need a lemma.

Lemma.

Suppose $A$, $B$, $C$, and $D$ are sets, with $A\mathrm{\cap }B\mathrm{=}C\mathrm{\cap }D\mathrm{=}\mathrm{\varnothing }$, and suppose there exist bijective maps $f_{\mathrm{1}}\mathrm{:}A\mathrm{\to }C$ and $f_{\mathrm{2}}\mathrm{:}B\mathrm{\to }D$. Thenthere exists a bijective map from $A\mathrm{\cup }B$ to $C\mathrm{\cup }D$.

Proof.

Define the map $g:A\cup B\to C\cup D$ by

(1)

To see that $g$ is injective, let $x_1,x_2\in A\cup B$, where $x_1\ne x_2$. If $x_1,x_2\in A$, then by the injectivity of $f_1$ we have

$$g(x_1)=f_1(x_1)\ne f_1(x_2)=g(x_2)\text{.}$$(2)

Similarly if $x_1,x_2\in B$, $g(x_1)\ne g(x_2)$ by the injectivity of $f_2$. If $x_1\in A$ and $x_2\in B$, then $g(x_1)=f_1(x_1)\in C$, while $g(x_2)=f_2(x_2)\in D$, whence $g(x_1)\ne g(x_2)$ because $C$ and $D$ are disjoint. If $x_1\in B$ and $x_2\in A$, then $g(x_1)\ne g(x_2)$ by the same reasoning. Thus $g$ is injective. To see that $g$ is surjective, let $y\in C\cup D$. If $y\in C$, then by the surjectivity of $f_1$ there exists some $x\in A$ such that $f_1(x)=y$, hence $g(x)=y$. Similarly if $y\in D$, by the surjectivity of $f_2$ there exists some $x\in B$ such that $f_2(x)=y$, hence $g(x)=y$. Thus $g$ is surjective.∎

Theorem.

If $A$ and $B$ are finite sets with $A\mathrm{\cap }B\mathrm{=}\mathrm{\varnothing }$, then $\mathrm{\mid }A\mathrm{\cup }B\mathrm{\mid }\mathrm{=}\mathrm{\mid }A\mathrm{\mid }\mathrm{+}\mathrm{\mid }B\mathrm{\mid }$.

Proof.

Let $A$ and $B$ be finite, disjoint sets.If either $A$ or $B$ is empty, the result holds trivially, so suppose $A$ and $B$ are nonempty with $\mid A\mid =n\in \mathbb{N}$ and $\mid B\mid =m\in \mathbb{N}$. Then there exist bijections $f:{\mathbb{N}}_n\to A$ and $g:{\mathbb{N}}_m\to B$. Define $h:{\mathbb{N}}_n\to {\mathbb{N}}_{n+m}\setminus {\mathbb{N}}_m$ by $h(i)=m+i$ for each $i\in {\mathbb{N}}_n$. To see that $h$ is injective, let $i_1,i_2\in \mathbb{N}$, and suppose $h(i_1)=h(i_2)$. Then $m+i_1=m+i_2$, whence $i_1=i_2$. Thus $h$ is injective. To see that $h$ is surjective, let $k\in {\mathbb{N}}_{n+m}\setminus {\mathbb{N}}_m$. By construction, $m+1\le k\le m+n$, and consequently $1\le k-m\le n$, so $k-m\in {\mathbb{N}}_n$; therefore we may take $i=k-m$ to have $h(i)=k$, so $h$ is surjective. Then, again by construction, the composition $f\circ h^{-1}$ is a bijection from ${\mathbb{N}}_{n+m}\setminus {\mathbb{N}}_m$ to $A$, and as such, by the preceding lemma, the map $\varphi :{\mathbb{N}}_{n+m}\setminus {\mathbb{N}}_m\cup {\mathbb{N}}_m\to A\cup B$ defined by

(3)

is a bijection. Of course, the domain of $\varphi$ is simply ${\mathbb{N}}_{n+m}$, so $\mid A\cup B\mid =n+m$, as asserted.∎

Corollary.

Let ${\mathrm{\{}{A}_k\mathrm{\}}}_{k\mathrm{=}\mathrm{1}}^n$ be a family of mutually disjoint, finite sets. Then $\mathrm{\mid }{\mathrm{\bigcup }}_{k\mathrm{=}\mathrm{1}}^n{A}_k\mathrm{\mid }\mathrm{=}{\mathrm{\sum }}_{k\mathrm{=}\mathrm{1}}^n\mathrm{\mid }{A}_k\mathrm{\mid }$.

Proof.

We proceed by induction on $n$. In the case $n=2$, the the preceding result applies, so let $n\ge 2\in \mathbb{N}$, and suppose$\mid {\bigcup }_{k=1}^n{A}_k\mid ={\sum }_{k=1}^n\mid A_k\mid$. Then by our inductive hypothesis and the preceding result, we have

$$\left|\bigcup _{k=1}^{n+1}{A}_k\right|=\left|\bigcup _{k=1}^n{A}_k\cup A_{n+1}\right|=\left|\bigcup _{k=1}^n{A}_k\right|+\mid A_{n+1}\mid =\sum _{k=1}^n\mid A_k\mid +\mid A_{n+1}\mid =\sum _{k=1}^{n+1}\mid A_k\mid \text{.}$$(4)

Thus the result holds for $n+1$, and by the principle of induction, for all $n$.∎