proof of pigeonhole principle
It will first be proven that, if a bijection exists between two finite sets, then the two sets have the same number of elements. Let and be finite sets and be a bijection. The claim will be proven by induction on .
If , then , and can only be surjective if .
Assume the statement holds for any set with . Let . Let with . Let . Then .
Define by . Since , for all . Thus, to show that is well-defined, it only needs to be verified that for all . This follows immediately from the facts that and is injective. Therefore, is well-defined.
Now it need to be proven that is a bijection. The fact that is injective follows immediately from the fact that is injective. To verify that is surjective, let . Since is surjective, there exists with . Since and is injective, . Thus, . Hence, . It follows that is a bijection.
By the induction hypothesis, . Thus, . Therefore, . ∎