Are there rigorous formulation and proof of the pigeonhole principle?

Question

The well known and intuitive pigeonhole principle states that if $n$ items are put in $m$ containers, and $n>m$, then there is at least one container which has more than one object.

I've always relied on this principle when solving combinatorics problems for the mathematical olympiads, where a high level of formalization is not necessary, but recently I've seen it in a group theory proof, so I wonder: is there a mathematically formal and rigorous formulation of this principle and, if so, what is its proof?

Answer 1

Yes and no. A fairly precise statement of the pigeonhole principle would be:

If $A$ and $B$ are sets, and $A$ has more elements than $B$, and $f$ is a function $A\to B$, then $f$ is not injective.

Can it be proved? That depends. In particular, what does "$A$ has more elements than $B$" mean? In the usual development of set theory we use this phrase to mean the same as "$A$ has larger cardinality than $B$", which again means

There is an injective function $B\to A$, but there is no injective function $A\to B$.

So if we use that as our definition, the pigeonhole principle is not a matter of proof -- instead it is part of the definition of what it means for one set to be larger than the other.

Of course, once we define natural numbers, we might want to prove a "finite pigeonhole principle":

If $m$ and $n$ are naturals, and $m>n$, and $A$ has $m$ elements and $B$ has $n$ elements, and $f$ is a function $A\to B$, then $f$ is not injective.

Then all we have to do is to prove this from a definitions of "has $m$ elements" and "$m<n$".

The first of these is fairly easily done, because in the usual development, the natural number $m$ is represented by the set $\{0,1,2,\ldots,m-1\}$ and "has $m$ elements" means to be in bijective correspondence by precisely that set. So when we strip away those bijections, what we have to prove is that if $m>n$ and $f:m\to n$, then $f$ is not injective.

This would be trivial (and pointless) if we're using the cardinality definition of what $m>n$ means -- so even though that is the most common choice, let's assume that we want to define $m>n$ to mean "there is a natural $a$ such that $n+a+1=m$.

The actual content of the proof now is to show that these two competing definitions of $>$ agree! Of course we first need to define addition, but once we have done that, it is a fairly simple matter of induction.

First we prove that $|m+1|>|m|$ (as cardinals) for all $m$. The base case $m=0$ is easy. $0$ is the empty set, so there is no function for $1\to 0$ at all, so in the impossible case that we get one, we can safely claim it will be non-injective.

For the induction case, assume that $|m+1|>|m|$ and we need to show that $|m+1+1|>|m+1|$. Let $f: (m+1+1)\to(m+1)$ be given, and let $b=f(m+1)$

$$g:(m+1)\to m : x \mapsto\begin{cases}f(x) & \text{when }f(x)\ne m \\ b & \text{when }f(x)=m \end{cases}$$

Then by the induction hypothesis $g$ is not injective, so there is $p$ and $q$ with $g(p)=g(q)$. If $f(p)=f(q)$ then $f$ is not injective, and we're done. Otherwise $f(p)\ne f(q)$, but this can only be the case if one of them is $m$ and the other is $b$. But then either $f(p)$ or $f(q)$ equals $f(m+1)$, and $f$ is again not injective.

Now to complete the proof, we just have to handle the case where $a\ne 0$ in $|m+a+1|>|m+1|$. By this time we hopefully know that addition is commutative and associative, so $m+a+1=m+1+a$. And so if we have $f:(m+a+1)\to (m+1)$, then it is also $((m+1)+a)\to(m+1)$, and its restriction to $(m+1)$ is not injective. A restriction of an injective function would itself be injective, so $f$ is not injective. (Whew!).

(... except that we also ought to prove along the way that $p+a\subseteq p$ with the standard representation of the natural numbers; otherwise restricting the last $f$ to $(m+a)$ doesn't make sense).

---

For a third option, we could also have said that $m>n$ means that $n\in m$ for the set representation of the numbers. That would need a different proof from the induction above.

But all in all, these proofs are not very enlightening about the pigeonhole principle. Intuitively I would say that the pigeonhole principle is itself at least as obvious as it is that $n+a+1=m$ is a good definition of $m>n$. So what the proof actually proves could be argued to be just that the $n+a+1$ definition is reasonable. And this would also be the case for the $n\in m$ alternative.

Answer 2

If $f:X\rightarrow Y$ is a map, with $X$ and $Y$ finite sets and $\mathrm{card} \ X> \mathrm{card} \ Y$ then $f$ cannot be injective. (The proof is obivous. Upon request: if $f$ were injective, then $\mathrm{card} \ X=\mathrm{card} \ f(X) \leqslant \mathrm{card} \ Y$ which is a contradiction.)

Answer 3

For any class $S$ and natural number $n$, define $\#(S) = n$ to mean that $n$ is the minimum natural number such that there is a injection $f$ from $S$ into $\mathbb{N}_{< n}$. Note that if there is an injection from $S$ into $\mathbb{N}_{<k}$ for some $k \in \mathbb{N}$, the existence of the minimum such $k$ follows from the well-ordering which is equivalent to induction. If we say that $S$ is finite if such an injection exists, then we have pigeonhole for any finite sets $S$ and $T$ such that $\#(S) > \#(T)$, simply by definition as follows. If there is an injection $f$ from $S$ to $T$, let $g$ be an injection from $T$ into $\mathbb{N}_{< \#(T)}$, and then $g \circ f$ is an injection from $S$ into $\mathbb{N}_{< \#(T)}$, which implies that $\#(T) \le \#(S)$, which is a contradiction.

Note that the above is a proof only for the finite case, but uses only Peano arithmetic, and is most in line with intuition. The intuition is that if you have $n$ distinct objects, you need at least $n$ natural numbers to label them all such that each has a different label, hence any injection (different labels for different objects) cannot use only natural numbers from $0$ to strictly less than $n-1$. And we want to use the least possible labels, which we can by the well-ordering principle. This application of the well-ordering principle can itself be proven from induction intuitively. It starts by asking, can we use only labels less than $0$? If so, $0$ is the minimum possible. If not, can we use only labels less than $1$? If so, $1$ is the minimum possible. If not, can we use only labels less than $2$? ... If there is no minimum, there will not be any labeling that uses bounded labels, which intuitively happens when we have infinitely many distinct objects, and so we use this labeling criterion to define finiteness.

Answer 4

Theorem: Let $n_i$, $1\leq i \leq n$ be a collection of natural numbers such that $\sum_i n_i >n$. Then $\exists i: n_i > 1$.

Proof: assume that $\forall i: n_i\leq 1$. Then $\sum_i n_i \leq n\cdot 1 < \sum_i n_i$, contradiction. $\square$

I don't claim this is the ultimate proof for the pigeon hole principe; what you consider the ultimate proof depends on what axioms you feel most comfortable with. In particular, if someone thinks the pigeon hole principle is sufficiently basic to use as an axiom, then I'm fine with that. It is, however, the way I internally justify the principle whenever feel uncomfortable using it, based on principles that I do feel comfortable with.

Exercise: Let $n_i$, $1\leq i \leq n$ be a collection of natural numbers such that $\sum_i n_i >m$. Then $\exists i: n_i > m/n$.

Answer 5

Let $X$ be a (finite) set of order $n$, and let $S_1, \dots, S_m\subset X$ with $\bigcup S_i = X$. The pigeonhole principle then asserts that if $m < n$, then some $\#S_i > 1$. For if all $\#S_i \leq 1$, then $n = \#X \leq \#S_1 + \cdots + \#S_m \leq m$.

Answer 6

A proof by induction on $m$ is quite flexible in terms of how it's formalised, that is to say "basically the same proof" will work in different systems. Outline:

Base case $m = 1$, if more than one item is put in exactly one box, then that box contains all the items. So at least one box has more than one item.

Suppose for the inductive step that whenever more than $k$ items are placed in exactly $k$ boxes then at least one box contains more than one item.

Now, place more than $k+1$ items in exactly $k+1$ boxes. Consider two cases of what is in the first box:

• More than one item. Then one of the boxes (namely the first) contains more than one item.
• 1 or 0 items. Then the remaining items (of which there are more than $k + 1 - 1 = k$) were placed in the other boxes (of which there are exactly $k$) and therefore by the inductive hypothesis one of the boxes contains more than one item.

So either way, at least one box contains more than one item and the induction is complete.

---

Note: if feeling brave, take the base case as $m = 0$, and state/show that it is not possible to put more than $0$ items into $0$ boxes at all. Proofs by induction where the base case is vacuously true are more fun ;-)

---

Now, how to rigorously formalise this proof depends firstly on how you formalise "putting items in boxes", and secondly on how you formalise the natural numbers. You could do the latter either by axiomatizing a Peano system or using the common set-theoretical construction. You could do the former either by defining a partition of a set with $n$ elements, where there are $m$ sets in the partition, so $x \in y$ means "item $x$ is in box $y$". Or (equivalently) by a function from a set of size $n$ to a set of size $m$, where $f(x) = y$ means "item $x$ is in box $y$". Or some other way. But in order to talk about the size of a set, we need a formalisation of "size" too. Developing that and showing the necessary properties is potentially the first two or more lectures of a "foundations of mathematics" course, and if anyone can fit it in a reasonably-sized answer to this question then I tip my hat to them! I'm reminded of Russell and Whitehead's Principia Mathematica, where page 379 contains proposition 54.43, together with the remark "From this proposition it will follow, when arithmetical addition has been defined, that $1 + 1 = 2$". A fully formal statement and proof of even the simplest thing can be a major undertaking, it's all a matter of where you start.

I reckon you can fill out the details in my proof by induction in any formalism you're inclined to choose, because all I need is the principle of induction, the ability to consider the first box, the ability to consider "the remaining items" after discounting 0 or 1 of them, and a lemma I snuck past without stating, that if you have $n$ items and set one aside then there are $n-1$ others. That can be proved by induction and used, together with some arithmetic, to prove the two claims in the inductive step about the numbers of the remaining items and remaining boxes.

There's probably some really good way to formalise these features (plus anything else I used without noticing), and then show that any logical system that has those things proves its own version of the Pigeonhole Principle, but I don't have the theory to do that myself. Similarly, each of the other answers here uses certain properties of the system it works in, and wherever those properties can be assumed or proved, that proof of the Principle works.

Answer 7

A nice way to state this which doesn't rely on counting (and works with cardinality rather than just the finite size of a set) would be to phrase it as follows:

Let $P$ be a set and $S$ be a partition of $P$ with $|S|<|P|$. There is some $s\in S$ with at least two elements.

which, intuitively says that, in the finite case, if $P$ has $n$ elements, then any partition of it into $n-1$ or fewer sets will have one element of the partition with multiple members. The proof of this is easy. If we define $f:P\rightarrow S$ to be the function such that $p\in f(p)$ - that is, $f(p)$ is the element of the partition containing $p$ - then, it follows that the preimage $f^{-1}[S]=S$. If every $S$ had at most one element, this would be equivalent to saying that $f$ is injective and therefore that $|S|\geq|P|$. Since, on the contrary, $|S|<|P|$ it must be that $f$ is not injective and therefore that some $S$ has more than one element.

This suffices to show a statement like, "You cannot partition $\mathbb R$ into countably many bins without one bin having multiple elements" at the same time as "If you have a set of $n$ pigeons, you cannot partition them into $n-1$ holes without having one hole with at least $2$ pigeons"

---

Notice that this proof does require knowing that the cardinality of $A=\{1,2,\ldots,i\}$ is greater than that of $B=\{1,2,\ldots,j\}$ for $i>j$. We can prove this by induction on $j$. It clearly holds for $j=0$, since there is no function to the empty set from a non-empty set. For the inductive step, notice that if $f:A\rightarrow B$ is an injection, then $$g(a)=\begin{cases}f(a) &&\text{if }f(a)<f(i)\\f(a)-1 &&\text{if }f(a)>f(i)\end{cases}$$ is an injection $\{1,2,\ldots,i-1\}\rightarrow\{1,2,\ldots,j-1\}$, which cannot exist by inductive hypothesis.

Answer 8

Further to the accepted answer here, and seven years and 5 months later, for what it's worth, here is my machine-verified, formal proof of a non-numeric version of the Pigeonhole Principle. It makes use of my own non-standard, but fairly intuitive form of natural deduction. It does not require the sets of "pigeons" or "pigeonholes" to be finite or even countable.