Understanding the mathematical definition of The Pigeonhole Principle.

Question

The Pigeonhole Principle states that if you have $n$ pigeons and $n-1$ pigeonholes, then at least one of those holes must contain at least $\lceil{\frac{n}{n-1}}\rceil$ many pigeons. So if you have $3$ pigeonholes and $11$ pigeons, then there is at least one hole with at least $3$ pigeons. That's a more informal definition.

A proper mathematical definition of the Pigeonhole Principle in my textbook states:

If $f : X \to Y$ is a mapping and $|X| >|Y|$, then there is a $y \in Y$ with $|f^{-1}(y)| \geq 2$.

The last part of this definition is a bit tricky for me to understand. So what it's saying is that; if we have a mapping from $X$ to $Y$ and the number of elements in $X$ (the number of pigeons) is larger than the number of elements in $Y$ (the number of pigeonholes), then there exist an element (pigeonhole) in $Y$ which has $2$ different preimage elements.

Is my understanding of the definition correct?

PS - The definition and explanation are translated from German, therefore some of the words may sound a bit weird, such as "preimage". In German it's "Urbild", which refers to the inverse image of an element in a set.

Answer 1

That's correct. $X$ is the set of pigeons, $Y$ is the set of pigeonholes, and $f(x)$ is the pigeonhole in which the pigeon $x$ is located. $f^{-1}(y)$ is therefore the set of pigeons in the pigeonhole $y$.

Answer 2

If you have $3$ pigeonholes and $11$ (or $10$) pigeons, then you must have at least $3$ (even $4$) pigeons in one pigeonhole. But what do you use for $n$ to get this from the statement in your first sentence? $n$ pigeons in $n-1$ holes is only a very special case of the pigeonhole principle. The real pigeonhole principle says:

If you put $n$ pigeons into $k$ holes, then you will have at least $\left\lceil\frac nk\right\rceil$ pigeons in one hole.

Restated in terms of sets and mappings:

If $X,Y$ are finite sets, $Y\ne\emptyset$, and $f:X\to Y$, then there is $y\in Y$ with $|f^{-1}(y)|\ge\left\lceil\frac{|X|}{|Y|}\right\rceil$.

There are also pigeonhole principles for infinite sets, for example:

If you put an infinite number of pigeons into a finite number of holes, then there will be an infinite number of pigeons in one hole.

Also:

If you put uncountably many pigeons into countably many holes, then there will be uncountably many pigeons in one hole.

Etc.

Answer 3

A simpler (but equivalent) mathematical definition of the Pigeonhole Principle is

If $f : X \to Y$ is a mapping between finite sets and $|X| >|Y|$, then $f$ is not injective.

That is, there are $x_1 \ne x_2 \in X$ such that $f(x_1)=f(x_2)$.