📂Lemmas

Pigeonhole Principle

Theorem ¹

Let the finite sets $A_{1} , \cdots , A_{n}$ be pairwise disjoint, and suppose that the cardinality of their union is greater than $nr$ for some $r \in \mathbb{N}$. Then there exists at least one set $A_{k}$ whose cardinality is greater than $r$: $$ \left| A_{1} \cup \cdots \cup A_{n} \right| > nr \implies \exists k : \left| A_{k} \right| > r $$

Explanation

Pigeonhole principle formalizes, as the name suggests, the idea that “if pigeons enter pigeonholes and there are more pigeons than pigeonholes, then at least one pigeonhole contains two or more pigeons.” It is used routinely throughout combinatorics.

Proof

We prove this by proof by contradiction. Assume that for every $k$ we have $\left| A_{k} \right| \le r$. Since we assumed the $A_{k}$ are disjoint, the cardinality of $\bigcup_{k=1}^{n} A_{k}$ is as follows. $$ \begin{align*} & \left| A_{1} \cup \cdots \cup A_{n} \right| \\ =& \left| A_{1} \right| + \cdots + \left| A_{n} \right| \\ \le& \underbrace{r + \cdots + r}_{n \text{ times }} \\ =& nr \end{align*} $$ This contradicts the assumption, so there exists at least one $k$ that is $\left| A_{k} \right| > r$.

■