# 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$. Then
there 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

$$g(x)=\{\begin{array}{cc}{f}_{1}(x)\hfill & \text{if}x\in A\hfill \\ {f}_{2}(x)\hfill & \text{if}x\in B\hfill \end{array}\text{.}$$ | (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

$$\varphi (i)=\{\begin{array}{cc}(f\circ {h}^{-1})(i)\hfill & \text{if}i\in {\mathbb{N}}_{n+m}\setminus {\mathbb{N}}_{m}\hfill \\ g(i)\hfill & \text{if}i\in {\mathbb{N}}_{m}\hfill \end{array}\text{,}$$ | (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$. ∎

Title | cardinality of disjoint union of finite sets |
---|---|

Canonical name | CardinalityOfDisjointUnionOfFiniteSets |

Date of creation | 2013-03-22 16:31:05 |

Last modified on | 2013-03-22 16:31:05 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 17 |

Author | mathcam (2727) |

Entry type | Theorem^{} |

Classification | msc 03E10 |

Related topic | Cardinality |

Related topic | Bijection |

Related topic | DisjointUnion |

Related topic | Function |