The Pigeonhole Principle

# The Pigeonhole Principle

We are now going to look at a very elementary principle commonly referred to as the "Pigeonhole Principle." Suppose that you have $m$ pigeons and $n$ holes. Further suppose that $n < m$, that is, there are more pigeons than pigeonholes. Then it should be intuitively clear that if every of the $m$ pigeons is in one of the $n$ holes then there exists at least one pigeonhole that has more than one pigeon in it.

This rather simple principle can be formulated in terms of sets as given in the following theorem.

 Theorem 1 (The Pigeonhole Principle): If $A$ is a finite set with $m$ elements and $A_1, A_2, ..., A_n$ is a partitioning of $A$ and if $n < m$ then there exists at least one subset $A_i$ of $A$ where $i \in \{ 1, 2, ..., n \}$ such that $\lvert A_i \rvert > 1$.
• Proof: Let $A$ be a finite set such that $\lvert A \rvert = m$, and let $A_1, A_2, ..., A_n$ be a partitioning of $A$ and such that $n < m$. We will carry the rest of this proof by contradiction.
• Suppose that $\lvert A_i \rvert = 1$ for each $i = 1, 2, ..., m$. Since $A_1, A_2, ..., A_n$ is a partitioning of $A$, then by the addition principle we have that:
(1)
\begin{align} \quad \lvert A \rvert = \sum_{i=1}^{n} A_i = \underbrace{1 + 1 + ... + 1}_{\mathrm{n-times}} = n \end{align}
• Therefore $\lvert A \rvert = n$. However, we also know that $\lvert A \rvert = m$. Thus $m = n$, but this is a contradiction since $n < m$. Therefore there exists at least one subset $A_i$ of $A$ for $i \in \{ 1, 2, ..., n \}$ such that $\lvert A_i \rvert > 1$. $\blacksquare$

The pigeonhole principle can be extended to have a wide range of applications. In stating these results, we will first need to define some types of functions.

 Definition: Let $A$ and $B$ be sets. A function $f : A \to B$ is said to be Injective or One-to-One if for all $x, y \in A$ where $x \neq y$ we have that $f(x) \neq f(y)$. The function $f$ is said to be Surjective or Onto if for every $y \in B$ there exists an $x \in A$ such that $f(x) = y$. The function $f$ is said to be Bijective if $f$ is both injective and surjective.

Instead of calling a function $f$ an "injective", "surjective", or "bijective" function, it is common to just call $f$ either an "injection", "surjection", or "bijection".

One application of the pigeonhole principle you might be aware of is with regarding these injective/surjective functions.

 Theorem 2: Let $A$ and $B$ be nonempty finite sets and let $f : A \to B$. a) If $\lvert A \rvert > \lvert B \rvert$ then $f$ is not injective. b) If $\lvert A \rvert < \lvert B \rvert$ then $f$ is not surjective.

We will prove neither of the results in Theorem 2 as they are not particularly related to combinatorics.