Proof of the generalized pigeonhole principle

Proof

We argue by contradiction.

1. Let $A$ and $B$ be finite sets, let $f : A \to B$ be a function, and let $n$ be a natural number with $|B| \cdot n < |A|$.
2. For $b \in B$, write $A_b = f^{-1}(b) = \set{a \in A : f(a) = b}$. Each $A_b$ is a subset of the finite set $A$, so it is finite.
3. Suppose, for a contradiction, that $|A_b| \le n$ for every $b \in B$.
4. The sets $A_b$ for $b \in B$ are pairwise disjoint. Indeed, if $a \in A_b \cap A_{b'}$, then $b = f(a) = b'$.
5. Their union is $A$, because each $a \in A$ lies in $A_{f(a)}$.
6. By the rule of sum, applied to the $|B|$ pairwise disjoint finite sets $A_b$, we get $|A| = \sum_{b \in B} |A_b|$.
7. By step 3, each term of this sum is at most $n$, and there are $|B|$ terms. So $|A| \le |B| \cdot n$.
8. This contradicts the hypothesis $|B| \cdot n < |A|$ of step 1.
9. Hence some $b \in B$ has $|f^{-1}(b)| > n$, that is, its fibre has cardinality greater than $n$.