1
$\begingroup$

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.

$\endgroup$

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.