Are there rigorous formulation and proof of the pigeonhole principle?
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?
$\endgroup$ 89 Answers
$\begingroup$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.
$\endgroup$ 2 $\begingroup$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$.
$\endgroup$ 7 $\begingroup$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.
$\endgroup$ $\begingroup$To add to the proofs offered here, I recently drafted a computer verified proof of the Pigeonhole Principle in Coq. I proceed using a proof by contradiction.
I first prove that, if each container is either empty or contains a single item, the number of items in all of the containers must be less than the number of containers (num_things_num_containers). Then I show that if, the total number of items in all of the containers is more than the number of containers then the assumption that all of the containers were either empty or contained a single item is false (lemma_0). I then show that this is equivalent to saying that there exists a container that is not empty or contains a single value (lemma_1). Finally I conclude by showing that this statement is equivalent to saying that there exists an element that contains more than one item, which proves the pigeonhole principle.
The full development can be found here: .
(** This module presents a proof of the pigeon hole principle, which states that if you place n things into m containers, and n > m, then one or more of the containers have more than one thing in it. Our proof proceeds by contradiction. We first show that if we have a collection of containers, cs, where every container is either empty or has a single item in it, then the number of items contained in all of the containers is less than or equal to the number of containers. Then we show that if, the number of items contained within a collection of containers is greater than the number of containers, and every container is either empty or has a single item in it, we have a contradiction. Accordingly, we cannot place n items into m collections without placing more than one item in a single container. Copyright (C) 2018 Larry D. Lee Jr. <> This program is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this program. If not, see <
*)
Require Import base.
Require Import List.
Require Import Lt. (* for le_not_lt *)
Require Import Compare_dec. (* for le_dec *)
Require Import PeanoNat. (* for Nat.nle_succ_0 *)
(** * I. Basic Concepts *)
(** Represents things (such as pigeons). *)
Parameter thing : Set.
(** Represents containers (such as cubbies). *)
Definition container := list thing.
(** Represents some collection of containers. *)
Definition containers := list container.
(** Counts the number of things in a container. *)
Definition container_num_things := length (A := thing).
(** Counts the number of containers. *)
Definition num_containers := length (A := container).
(** Counts the number of things in some containers. *)
Definition num_things (cs : containers) : nat := fold_right (fun c n => container_num_things c + n) 0 cs.
(** Accepts a container and asserts that it is either empty or has only one item in it.
*)
Definition container_ok (c : container) : Prop := container_num_things c <= 1.
(** This lemma proves that the OK predicate is decideable. Note: we will need this when proving that [~ Forall container_ok] implies [Exists ~ container_ok].
*)
Definition container_ok_dec : forall (c : container), {container_ok c}+{~ container_ok c} := fun c => le_dec (container_num_things c) 1.
(** Accepts a set of containers and asserts that all of the containers are either empty or only contain a single item.
*)
Definition containers_ok (cs : containers) : Prop := Forall container_ok cs.
(** * II. Auxiliary Theorems *)
(** Accepts a predicate, [P], and a list, [x0 :: xs], and proves that if [P] is true for every element in [x0 :: xs], then [P] is true for every element in [xs].
*)
Definition Forall_tail : forall (A : Type) (P : A -> Prop) (x0 : A) (xs : list A), Forall P (x0 :: xs) -> Forall P xs := fun _ P x0 xs H => let H0 : forall x, In x (x0 :: xs) -> P x := proj1 (Forall_forall P (x0 :: xs)) H in let H1 : forall x, In x xs -> P x := fun x H2 => H0 x (or_intror (x0 = x) H2) in proj2 (Forall_forall P xs) H1.
Arguments Forall_tail {A} {P} x0 xs.
(** Accepts two predicates, [P] and [Q], and a list, [xs], and proves that, if [P -> Q], and there exists an element in [xs] for which [P] is true, then there exists an element in [xs] for which [Q] is true.
*)
Definition Exists_impl : forall (A : Type) (P Q : A -> Prop), (forall x : A, P x -> Q x) -> forall xs : list A, Exists P xs -> Exists Q xs := fun _ P Q H xs H0 => let H1 : exists x, In x xs /\ P x := proj1 (Exists_exists P xs) H0 in let H2 : exists x, In x xs /\ Q x := ex_ind (fun x H2 => ex_intro (fun x => In x xs /\ Q x) x (conj (proj1 H2) (H x (proj2 H2)))) H1 in (proj2 (Exists_exists Q xs)) H2.
Arguments Exists_impl {A} {P} {Q} H xs H0.
(** * III. Fundamental Proof *)
(** This theorem proves that given a collection of containers, where every container is either empty or has one item in it, then the number of items contained in all of the containers must be less than or equal to the number of containers.
*)
Definition num_things_num_containers : forall cs : containers, containers_ok cs -> num_things cs <= num_containers cs := let T cs := containers_ok cs -> num_things cs <= num_containers cs in list_ind T (* I. case where there are no containers. *) (fun _ => le_0_n 0) (* II. case where there is more than one container. *) (list_ind (fun xs => forall cs, T cs -> T (xs :: cs)) (* II.A. case where the first container is empty. *) (fun cs (H : T cs) (H0 : containers_ok (nil :: cs)) => let H1 : num_things cs <= num_containers cs := H (Forall_tail nil cs H0) in (le_S (0 + num_things cs) (num_containers cs) (H1 || a <= num_containers cs @a by plus_O_n (num_things cs)))) (* II.B. case where the first container has one or more things in it. *) (fun x0 => list_ind (fun xs => _ -> forall cs, T cs -> T ((x0 :: xs) :: cs)) (* II.B.1. case where the first container has only one thing in it. *) (fun _ cs (H : T cs) (H0 : containers_ok ((x0 :: nil) :: cs)) => let H1 : num_things cs <= num_containers cs := H (Forall_tail (x0 :: nil) cs H0) in le_n_S (num_things cs) (num_containers cs) H1 || a <= S (num_containers cs) @a by Nat.add_1_l (num_things cs)) (* II.B.2. case where the first container has two or more things in it. *) (fun x1 xs _ _ cs (H : T cs) (H0 : containers_ok ((x0 :: x1 :: xs) :: cs)) => False_ind (num_things ((x0 :: x1 :: xs) :: cs) <= num_containers ((x0 :: x1 :: xs) :: cs)) ((Nat.nle_succ_0 (length xs)) (le_S_n (S (length xs)) 0 ((Forall_inv H0) : S (S (length xs)) <= 1)))))).
(** * IV. The Pigeonhole Principle *)
(** This lemma proves that if we have a collection of containers and the number of things in the containers is greater than the number of the containers then not all of the containers can be empty or have only one thing in it.
*)
Definition lemma_0 : forall cs : containers, num_things cs > num_containers cs -> ~ containers_ok cs := fun cs (H : num_containers cs < num_things cs) (H0 : containers_ok cs) => le_not_lt (num_things cs) (num_containers cs) (num_things_num_containers cs H0) H.
(** This lemma proves that if we have a collection of containers and the number of things in the containers is greater than the number of containers, then one of the containers cannot be empty or have only one item in it.
*)
Definition lemma_1 : forall cs : containers, num_things cs > num_containers cs -> Exists (fun c : container => ~ container_ok c) cs := fun cs H => neg_Forall_Exists_neg container_ok_dec (lemma_0 cs H).
(** This theorem proves that if we are given a collection of containers and the number of things in those containers is greater than the number of containers, then one or more of the containers has more than one thing in it.
*)
Definition pigeonhole_principle : forall cs : containers, num_things cs > num_containers cs -> Exists (fun c : container => container_num_things c > 1) cs := fun cs H => Exists_impl (fun c (H0 : ~ container_ok c) => not_le (container_num_things c) 1 H0) cs
(lemma_1 cs H).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$.
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$ 8 $\begingroup$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.
$\endgroup$ 1 $\begingroup$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.)
$\endgroup$ 8
