1. 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.

2. 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.

3. 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]$.