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 $\displaystyle f: \mathbb{N}_{m} \to X $ and $\displaystyle f: \mathbb{N}_{n} \to X $ are bijections with the same codomain, then $\displaystyle m = n $). Namely, it says the following: Suppose that $\displaystyle X $ and $\displaystyle Y $ are finite, non-empty sets such that $\displaystyle |X| > |Y|$. Then $\displaystyle f: X \to Y $ is not an injection.