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}\rightarrow A$ and $g:\mathbb{N}_{m}\rightarrow A$. Since $g$ is a bijection, it is invertible   , and $g^{-1}:A\rightarrow\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\geq 1\in\mathbb{N}$, and suppose that, for all $m\in\mathbb{N}$, the existence of a bijection $f:\mathbb{N}_{n}\rightarrow\mathbb{N}_{m}$ implies $n=m$. Let $m\in\mathbb{N}$ and suppose $h:\mathbb{N}_{n+1}\rightarrow\mathbb{N}_{m}$ is a bijection. Let $k=h(n+1)$, and notice that $1\leq k\leq 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 $\phi:\mathbb{N}_{n}\rightarrow\mathbb{N}_{m-1}$ by $\phi(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\neq n+1$, and define $\phi:\mathbb{N}_{n}\rightarrow\mathbb{N}_{m-1}$ by

 $\phi(i)=\begin{cases}h(i)&\text{if }i\neq j\\ k&\text{if }i=j\\ \end{cases}\text{.}$

We first show that $\phi$ is one-to-one. Let $i_{1},i_{2}\in\mathbb{N}_{n}$, where $i_{1}\neq 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

 $\phi(i_{1})=h(i_{1})\neq h(i_{2})=\phi(i_{2})\text{.}$

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

 $\phi(i_{1})=k=h(n+1)\neq h(i_{2})=\phi(i_{2})\text{.}$

Similarly it can be shown that, if $i_{2}=j$, $\phi(i_{1})\neq\phi(i_{2})$, so $\phi$ is one-to-one. We now show that $\phi$ is onto. Let $l\in\mathbb{N}_{m-1}$. If $l=k$, then we may take $i=j$ to have $\phi(i)=\phi(j)=k=l$. If $l\neq 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}\rightarrow\mathbb{N}_{m}$, we may conclude that $m=n$, and consequently that the cardinality of $A$ is unique, as desired. ∎

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 $m, and suppose $f:A\rightarrow B$ is a bijection. By hypothesis   there exist bijections $g:\mathbb{N}_{n}\rightarrow A$ and $h:\mathbb{N}_{m}\rightarrow 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