Naive set theory: Functions
Dirichlet's box principle / pigeonhole principle
If you store four objects in three drawers, you can be sure that there is at least one drawer with at least two objects. Indeed, if each drawer contains at most one object, then there would be at most three objects in total, which contradicts the fact that four objects have been stored. This is an example of Dirichlet's drawer principle.
It is also known as the pigeonhole principle: If a number of pigeons must go into lofts in a dovecote,
and there are more pigeons than lofts, then at least one loft must contain two pigeons.
Somewhat more generally, the pigeonhole principle can be formulated as follows:
The generalized pigeonhole principle If \(m\) objects are distributed into \(n\) containers with \(m \ge 1\) and \(n \ge 1\), then there is at least one container with at least \(\lceil m/n\rceil\) objects, where \(\lceil x\rceil\) is the smallest integer that is greater than or equal to \(x\).
Consequence of the above principle for set theory:
Let \(f:\; X\rightarrow Y\) be a function from a non-empty finite set \(X\) with \(m\) elements to a non-empty finite set \(Y\) with \(n\) elements. Then:
- if \(m > n\), then \(f\) is not injective;
- if \(m < n\), then \(f\) is not surjective.
There exists an even stronger pigeonhole principle:
Strong form of the pigeonhole principle. Let \(q_1,q_2,\ldots, q_n\) be \(n\) natural numbers greater than \(0\). If \(q_1 + q_2 + \cdots + q_n - n + 1\) objects are distributed into \(n\) containers, then at least one of the following statements is true:
- there are at least \(q_1\) objects in the first container;
- there are at least \(q_2\) objects in the second container;
\(\vdots\) - there are at least \(q_n\) objects in the \(n\)-th container.
