# Pigeonhole Principle

• Aug 30th 2007, 01:43 PM
shilz222
Pigeonhole Principle
How many proofs are there for the pigeonhole principle? I know of one proof that just uses composition of functions to develop lemmas, and then ultimately come up with the Pigeonhole principle. The proof starts with the basic problem of 2 different ways of counting sets (i.e if $f: \mathbb{N}_{m} \to X$ and $f: \mathbb{N}_{n} \to X$ are bijections with the same codomain, then $m = n$). Namely, it says the following: Suppose that $X$ and $Y$ are finite, non-empty sets such that $|X| > |Y|$. Then $f: X \to Y$ is not an injection.
• Aug 30th 2007, 01:48 PM
ThePerfectHacker
What is a finite set? It is a set such has no proper subset has a bijection with the full set. Use that fact and prove formally the principle.
• Aug 30th 2007, 03:15 PM
Plato
There are several proofs as you observe. This of is found in many discrete mathematics texts.
Given that $m = \left| X \right| > \left| Y \right| = n$, recall that $
X = \bigcup\limits_{y \in Y} {\overleftarrow f \left\{ y \right\}}$
.

Suppose that $\left( {\forall y \in Y} \right)\left[ {\left| {\overleftarrow f \left\{ y \right\}} \right| \le 1} \right]\quad$.

Using that we have $\left| X \right| = \left| {\bigcup\limits_{y \in Y} {\overleftarrow f \left\{ y \right\}} } \right| = \bigcup\limits_{y \in Y} {\left| {\overleftarrow f \left\{ y \right\}} \right|} \le n$ that is a contradiction.
Thus $\left( {\exists z \in Y} \right)\left[ {\left| {\overleftarrow f \left\{ z \right\}} \right| > 1} \right]$.

The value of this proof is that it also proves the generalized form. If we have m pigeons and n pigeonholes with $m > n$ the some hole contains at least $\left\lceil {\frac{m}{n}} \right\rceil$ pigeons (that is the ceiling function).

To see this proof use the assumptions above, using the supposition that $k = \left\lceil {\frac{m}{n}} \right\rceil \quad \& \quad \left( {\forall y \in Y} \right)\left[ {\left| {\overleftarrow f \left\{ y \right\}} \right| < k} \right]$.

This time $\left| X \right| = \left| {\bigcup\limits_{y \in Y} {\overleftarrow f \left\{ y \right\}} } \right| = \bigcup\limits_{y \in Y} {\left| {\overleftarrow f \left\{ y \right\}} \right|} \le n\left( {k - 1} \right) \le m$ that is a contradiction.
Thus $\left( {\exists z \in Y} \right)\left[ {\left| {\overleftarrow f \left\{ z \right\}} \right| \ge k} \right]$.