Natural Blogarithms

Favorite Theorem #6: Pigeonhole Principle

September 15th, 2006 by SplineGuy

In doing do preparatory reading for classes next term, I stumbled across this little interestingly named gem of a theorem. It is one that is frequently used in combinatorial analysis. It will also come in handy in our introductory Analysis class.

The reason for its name is that it can be used to say that if $m$ pigeons are put into $b$ pigeon holes and if $m>n$ the at least two pigeons must share one of the pigeonholes. To you non-mathematicians that see that as utterly obvious, just know that in the field of mathematics even the obvious concepts still need to be verified through rigorous proof.

So here it is, the pigeonhole principle:

Thm: Let $m,n \in \mathbb{N}$ with $m>n$ . Then there does not exist an injection from $N_m$ to $N_n$ .

(Note: $\mathbb{N}$ , is the set of natural numbers, and for some $k\in \mathbb{N}$ , $\mathbb{N}_k$ is the set of all natural numbers less than $k$

The only proof I’ve some up with is similar to the one that appears in Bartle and Sherbert’s Intro. to Real Analysis. It is below. If you have a more elegant argument, please share.

Proof:
Let’s use mathematical induction. If $n=1$ and if $f$ is any map of $\mathbb{N}_m \ (m>1)$ into $\mathbb{N}_1$ then it is clear that $f(1) = f(2) = \cdots = f(m)=1$ so that $f$ is not 1-1, and thus, not injective.
Now, assume that for some $k>1$ , we have that there is no injective map from $\mathbb{N}_m$ to $\mathbb{N}_k$ when $m>k$ . Let $f$ be a function that maps $\mathbb{N}_m$ to $\mathbb{N}_{k+1}$ . Consider two cases: either the image of $g$ is a subset of $\mathbb{N}_k$ or it is not.
Case 1: If $g(\mathbb{N}_m) \subseteq \mathbb{N_k}$ then we can consider $g$ as simply a map from $\mathbb{N}_m$ to $\mathbb{N}_k$ and by the induction hypothesis, it cannot be injective.
Case 2: Suppose that $g(\mathbb{N}_m)$ is not contained in $\mathbb{N}_k$ . If more than one element in $\mathbb{N}_m$ maps to $k+1$ , then $g$ is not an injection. Therefore, we assume that there is a single element $p\in \mathbb{N}_m$ such that $g(p)=k+1$ . Define
$h (q) = \left\{ \begin{array}{ll}g(q) & \mathrm{if } \ q=1,\ldots,p-1\\ g(q+1) & \mathrm{if } \ q=p, \ldots, m-1 \end{array}\right.$
Now, since $h:\mathbb{N}_{m-1} \rightarrow \mathbb{N}_k$ , the induction hypothesis applies and $h$ is not injective. It is then easy to see that $g$ is not injective.
Q.E.D.

Interestingly this can prove that if two different people count the same set of objects, they will get the same number (assuming they count correctly). Stated mathematically:

Thm: $S$ is a finite set $\Rightarrow \ \exists ! \ \ n \in \mathbb{N}$ such that $\exists$ a bijection from $\mathbb{N}_n$ to $S$ .