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 and are bijections with the same codomain, then ). Namely, it says the following: Suppose that and are finite, non-empty sets such that . Then is not an injection.