0
$\begingroup$

According to Wikipedia, an alternative formulation of the pigeonhole principle is (slighly adapted) that, if $n$ pigeons fly into $n+1$ empty holes, then some hole remains empty. While this principle looks like a close relative of the pigeonhole principle (if $n+1$ pigeons fly into $n$ holes, then some hole has two or more pigeons), and is just as commonsensical, I don't immediately see how to derive it from the pigeonhole principle or vice versa. It seems to me that, to call one principle "an alternative formulation" of another, it should be possible to derive each one readily from the other. Could someone please provide these derivations?

For ease of reference, proofs by induction of the pigeonhole principle (PP) and the variant (VPP) are given here.

For PP, the base case is for $n=1$: Clearly, if two pigeons fly into a hole, then that hole holds two or more pigeons. Suppose now that PP has been established for $n=k$, and we admit one more pigeon and one more hole. The new pigeon flies either into the new hole, which leaves the situation in the original holes unchanged—in particular, that some hole has two or more pigeons—or into an original hole. In the latter case, the number of pigeons in any of those holes does not decrease. In particular, any hole that held two or more pigeons—and, by supposition, there is at least one such hole—still has two or more pigeons. This establishes PP for the case $n=k+1$.

For VPP, the base case is for $n=0$: Obviously, if no pigeon flies into an empty hole, then that hole remains empty. Suppose now that VPP has been established for $n=k$, and we admit one more pigeon and one more hole. The new pigeon flies either into the new hole, which leaves the situation in the original holes unchanged—in particular, that some hole is empty—or into an original hole, leaving the new hole empty. Either way, some hole is empty, which establishes VPP for the case $n=k+1$.

$\endgroup$
1
  • 1
    $\begingroup$ all is simply map's injectivity $\endgroup$ – janmarqz Jun 13 '18 at 21:15
6
$\begingroup$

Let's suppose we have $n$ pigeons flying into $n+1$ holes. If no hole is missed, then we have a function from holes to pigeons sending each hole to some pigeon which winds up in it. By the pigeonhole principle as usually stated (with the words "pigeon" and "hole" swapped) this function is not injective: there are a pair of holes going to the same pigeon. But this means that one pigeon flew into at least two holes, which isn't how we're allowing pigeons to behave; so some hole must have been missed.

In the other direction, if I have $n+1$ pigeons fitting into $n$ holes, we can consider the map from holes to pigeons sending each hole to some pigeon filling it (or a random pigeon if it's unfilled). This is a map from a set of size $n$ to a set of size $n+1$; swapping the words "pigeon" and "hole," the alternate version of the pigeonhole principle you mention tells us that this map is not surjective. What does this mean for the original situation? Well, it means that there is some pigeon which our function doesn't "pick out." But (exercise) the only way for Fred the Unpopular Pigeon to not be picked is if some other pigeon, filling the same hole as Fred, was picked instead; and this means that two pigeons wound up in the same hole! So we've proved the usual pigeonhole principle from the modified form.


Abstractly, all this is exploring the relationship between injectivity, surjectivity, and cardinality.

  • The usual pigeonhole principle says, "There is no injective map from a set of size $n+1$ to a set of size $n$." More generally, for one set to "fit inside" another, the former can't have bigger cardinality than the latter.

  • The modified pigeonhole principle says, "There is no surjective map from a set of size $n$ to a set of size $n+1$." More generally, for one set to "cover" another, the former can't have smaller cardinality than the latter.

The following principle really captures what's going on here, and is what links the two pigeonhole facts above:

There is a surjection from $A$ to $B$ iff there is an injection from $B$ to $A$.

Somewhat off-topic remark: If you go further in set theory, you'll find that there's actually a surprising twist here: the statement above (specifically, the surjection-to-injection part) requires a somewhat subtle set-theoretic principle called the axiom of choice if we want to apply it to arbitrary infinite sets and not just finite sets. But that's a topic for a different post, I think.

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