# Understanding the mathematical definition of The Pigeonhole Principle.

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.

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$$.

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.

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)$$.