Skip to main content

# Section4.1The Pigeon Hole Principle¶ permalink

A function $f:X\longrightarrow Y$ is said to be $1$–$1$ (read one-to-one) when $f(x)\neq f(x')$ for all $x,x'\in X$ with $x\neq x'$. A $1$–$1$ function is also called an injection or we say that $f$ is injective. When $f:X\longrightarrow Y$ is $1$–$1$, we note that $|X|\le |Y|$. Conversely, we have the following self-evident statement, which is popularly called the “Pigeon Hole” principle.

In more casual language, if you must put $n+1$ pigeons into $n$ holes, then you must put two pigeons into the same hole.

Here is a classic result, whose proof follows immediately from the Pigeon Hole Principle.

##### Proof

In Chapter 11, we will explore some powerful generalizations of the Pigeon Hole Principle. All these results have the flavor of the general assertion that total disarray is impossible.