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

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

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