3
$\begingroup$

The pigeonhole principle is so obvious to me that I am not able to think of a proof based on the axioms of natural numbers. Can anyone please explain its proof clearly mentioning the axioms?

$\endgroup$
  • 1
    $\begingroup$ The pigeon-hole principle states that whenever $A$ has smaller cardinality than $B$, there does not exist a surjective map $A\to B$. This is the definition of "smaller cardinality". - So I suppose you want a proof by induction that $\{1,\ldots, n\}$ has smaller cardinality than $\{1,\ldots,m\}$ whenever $n<m$? $\endgroup$ – Hagen von Eitzen Oct 14 '16 at 9:35
  • $\begingroup$ Can we use the "order axioms" for natural numbers instead of defining "smaller" by a map ? $\endgroup$ – Rajkumar Oct 14 '16 at 10:01
  • $\begingroup$ Alternate formulation: if there exists a surjection $A \to B$ then there exists an injection $B \to A$. The pigeon-hole principle is the contrapositive of that (for $A$ = holes and $B$ = pigeons). $\endgroup$ – dxiv Oct 15 '16 at 3:57
  • $\begingroup$ @dxiv Well, the usual pigeonhole principle is the converse of that statement restricted to finite sets. Note that that more general statement requires (indeed, is equivalent to) the axiom of choice . . . $\endgroup$ – Noah Schweber Oct 15 '16 at 5:03
  • $\begingroup$ @NoahSchweber That's entirely correct, but the context here was pigeonhole'ing, which doesn't work for infinite sets anyway as you noted, AC or not. $\endgroup$ – dxiv Oct 15 '16 at 5:30
4
$\begingroup$

It can be proved by induction; so the crucial axiom is that the natural numbers are well-ordered, that is, any nonempty set of natural numbers has a least element.

For a proof of the pigeonhole principle, see my answer to this other question. (Strictly speaking, what's proved there isn't exactly the pigeonhole principle - instead, it's the statement "There is no injection from a set of $n$ elements to a set of $m$ elements, if $n>m$" - but it's easy to get from this to the pigeonhole principle.)

$\endgroup$
1
$\begingroup$

Here is a non-numeric version of the pigeonhole principle that may interest you. The formal proof is too long to post here (several hundred lines, see "The Pigeonhole Principle" at my math blog).

Let $P$ be the (non-empty) set of pigeons, and $H$ the set of holes. Suppose each pigeon is put in a hole. Suppose further that there are more pigeons than holes, i.e. that no function mapping holes to pigeons is surjective (onto).

Then at least two pigeons will be put in the same hole.

More formally:

$\exists a:a \in P\space\space$ i.e. there is at least one pigeon

$\implies \forall f:[f:P \to H\space \space\space$ i.e. each pigeon is put in a hole

$\land \forall g: [[g: H \to P]\implies g$ is not surjective] $\space \space$ i.e. there are more pigeons than holes

$\implies \exists b,c,d: [b\in P\land c\in P \land d\in H \land [b\ne c\land f(b)=d \land f(c)=d]]]\space \space$ i.e. at least two pigeons will be in the same hole.

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