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

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