# uniqueness of cardinality

###### Theorem.

The cardinality of a set is unique.

###### Proof.

We will verify the result for finite sets^{} only.
Suppose $A$ is a finite set with cardinality $\mid A\mid =n$ and $\mid A\mid =m$. Then there exist bijections $f:{\mathbb{N}}_{n}\to A$ and $g:{\mathbb{N}}_{m}\to A$. Since $g$ is a bijection, it is invertible^{}, and ${g}^{-1}:A\to {\mathbb{N}}_{m}$ is a bijection. Then the composition^{} ${g}^{-1}\circ f$ is a bijection from ${\mathbb{N}}_{n}$ to ${\mathbb{N}}_{m}$. We will show by induction^{} on $n$ that $m=n$. In the case $n=1$ we have ${\mathbb{N}}_{n}={\mathbb{N}}_{1}=\{1\}$, and it must be that ${\mathbb{N}}_{m}=\{1\}$ as well, whence $m=1=n$. Now let $n\ge 1\in \mathbb{N}$, and suppose that, for all $m\in \mathbb{N}$, the existence of a bijection $f:{\mathbb{N}}_{n}\to {\mathbb{N}}_{m}$ implies $n=m$. Let $m\in \mathbb{N}$ and suppose $h:{\mathbb{N}}_{n+1}\to {\mathbb{N}}_{m}$ is a bijection. Let $k=h(n+1)$, and notice that $1\le k\le m$. Since $h$ is onto there exists some $j\in {\mathbb{N}}_{n+1}$ such that $f(j)=m$. There are two cases to consider. If $j=n+1$, then we may define $\varphi :{\mathbb{N}}_{n}\to {\mathbb{N}}_{m-1}$ by $\varphi (i)=h(i)$ for all $i\in {\mathbb{N}}_{n}$, which is clearly a bijection, so by the inductive hypothesis $n=m-1$, and thus $n+1=m$. Now suppose $j\ne n+1$, and define $\varphi :{\mathbb{N}}_{n}\to {\mathbb{N}}_{m-1}$ by

$$\varphi (i)=\{\begin{array}{cc}h(i)\hfill & \text{if}i\ne j\hfill \\ k\hfill & \text{if}i=j\hfill \end{array}\text{.}$$ |

We first show that $\varphi $ is one-to-one. Let ${i}_{1},{i}_{2}\in {\mathbb{N}}_{n}$, where ${i}_{1}\ne {i}_{2}$. First consider the case where neither ${i}_{1}$ nor ${i}_{2}$ is equal to $j$. Then, since $h$ is one-to-one, we have

$$\varphi ({i}_{1})=h({i}_{1})\ne h({i}_{2})=\varphi ({i}_{2})\text{.}$$ |

In the case ${i}_{1}=j$, again because $h$ is one-to-one, we have

$$\varphi ({i}_{1})=k=h(n+1)\ne h({i}_{2})=\varphi ({i}_{2})\text{.}$$ |

Similarly it can be shown that, if ${i}_{2}=j$, $\varphi ({i}_{1})\ne \varphi ({i}_{2})$, so $\varphi $ is one-to-one. We now show that $\varphi $ is onto. Let $l\in {\mathbb{N}}_{m-1}$. If $l=k$, then we may take $i=j$ to have $\varphi (i)=\varphi (j)=k=l$. If $l\ne k$, then, because $h$ is onto, there exists some $i\in {\mathbb{N}}_{n}$ such that $h(i)=l$, so $g(i)=h(i)=l$. Thus $g$ is onto, and our inductive hypothesis again gives $n=m-1$, hence $n+1=m$. So by the principle of induction, the result holds for all $n$. Returning now to our set $A$ and our bijection ${g}^{-1}\circ f:{\mathbb{N}}_{n}\to {\mathbb{N}}_{m}$, we may conclude that $m=n$, and consequently that the cardinality of $A$ is unique, as desired. ∎

###### Corollary.

There does not exist a bijection from a finite set to a proper subset^{} of itself.

###### Proof.

Without a loss of generality we may assume the proper subset is nonempty, for if the set is empty then the corollary holds vacuously. So let $A$ be as above with cardinality $n\in \mathbb{N}$, $B$ a proper subset of $A$ with cardinality $$, and suppose $f:A\to B$ is a bijection. By hypothesis^{} there exist bijections $g:{\mathbb{N}}_{n}\to A$ and $h:{\mathbb{N}}_{m}\to B$; but then ${h}^{-1}\circ (f\circ g)$ is a bijection from ${\mathbb{N}}_{n}$ to ${\mathbb{N}}_{m}$, whence by the preceding result $n=m$, contrary to assumption^{}.
∎

The corollary is also known more popularly as the pigeonhole principle^{}.

Title | uniqueness of cardinality |

Canonical name | UniquenessOfCardinality |

Date of creation | 2013-03-22 16:26:52 |

Last modified on | 2013-03-22 16:26:52 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 27 |

Author | mathcam (2727) |

Entry type | Theorem |

Classification | msc 03E10 |

Related topic | cardinality |

Related topic | bijection |

Related topic | function |

Related topic | set |

Related topic | subset |

Related topic | Subset |

Related topic | Bijection |

Related topic | Set |

Related topic | PigeonholePrinciple |