Pigeonhole Principle

combinatorics

Definition

Pigeonhole Principle

Given two sets $A$ and $B$ with $1\le |B|<|A|$, then a relation $f:A\to B$ cannot be injective, meaning:

$$\exists x,y\in A:x\ne y\wedge f(x)=f(y)$$

In other words, since $|B|<|A|$, one cannot map a bigger set into a smaller set while preserving injectivity.