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$. ∎

Title cardinality of disjoint union of finite sets CardinalityOfDisjointUnionOfFiniteSets 2013-03-22 16:31:05 2013-03-22 16:31:05 mathcam (2727) mathcam (2727) 17 mathcam (2727) Theorem  msc 03E10 Cardinality Bijection DisjointUnion Function