## You are here

Homecardinality of disjoint union of finite sets

## Primary tabs

# 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\cap B=C\cap D=\emptyset$, and suppose there exist bijective maps $f_{1}:A\rightarrow C$ and $f_{2}:B\rightarrow D$. Then there exists a bijective map from $A\cup B$ to $C\cup D$.

###### Proof.

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

$g(x)=\begin{cases}f_{1}(x)&\text{if }x\in A\\ f_{2}(x)&\text{if }x\in B\end{cases}\text{.}$ | (1) |

To see that $g$ is injective, let $x_{1},x_{2}\in A\cup B$, where $x_{1}\neq 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})\neq f_{1}(x_{2})=g(x_{2})\text{.}$ | (2) |

Similarly if $x_{1},x_{2}\in B$, $g(x_{1})\neq 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})\neq g(x_{2})$ because $C$ and $D$ are disjoint. If $x_{1}\in B$ and $x_{2}\in A$, then $g(x_{1})\neq 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\cap B=\emptyset$, then $\mid A\cup B\mid=\mid A\mid+\mid B\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}\rightarrow A$ and $g:\mathbb{N}_{m}\rightarrow B$. Define $h:\mathbb{N}_{n}\rightarrow\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\leq k\leq m+n$, and consequently $1\leq k-m\leq 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 $\phi:\mathbb{N}_{{n+m}}\setminus\mathbb{N}_{m}\cup\mathbb{N}_{m}\rightarrow A\cup B$ defined by

$\phi(i)=\begin{cases}(f\circ h^{{-1}})(i)&\text{if }i\in\mathbb{N}_{{n+m}}% \setminus\mathbb{N}_{m}\\ g(i)&\text{if }i\in\mathbb{N}_{m}\end{cases}\text{,}$ | (3) |

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

###### Corollary.

Let $\{A_{k}\}_{{k=1}}^{n}$ be a family of mutually disjoint, finite sets. Then $\mid\bigcup_{{k=1}}^{n}A_{k}\mid=\sum_{{k=1}}^{n}\mid A_{k}\mid$.

###### Proof.

We proceed by induction on $n$. In the case $n=2$, the the preceding result applies, so let $n\geq 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

$\bigg|\bigcup_{{k=1}}^{{n+1}}A_{k}\bigg|=\bigg|\bigcup_{{k=1}}^{n}A_{k}\cup A_% {{n+1}}\bigg|=\bigg|\bigcup_{{k=1}}^{n}A_{k}\bigg|+\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$. ∎

## Mathematics Subject Classification

03E10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections