📂Lemmas

Pigeonhole Principle

Theorem ¹

finite sets $A_{1} , \cdots , A_{n}$ are pairwise disjoint, and assume 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 the idea that “if pigeons are placed into pigeonholes, and there are more pigeons than pigeonholes, then at least one pigeonhole contains two or more pigeons.” It is used routinely throughout combinatorics; for some, it may even be considered a theorem.

Proof

Proved by proof by contradiction. Assume for every $k$ that $\left| A_{k} \right| \le r$ holds; since the $A_{k}$ are pairwise disjoint, the cardinality of ▷eq09◯ 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$.

■