20
$\begingroup$

One version of the Pigeonhole principle says that if the cardinality of a set $A$ is greater than that of a set $B$, then there can be no one-to-one function that maps from $A$ to $B$.

Another version says: If $n$ elements are partitioned into $m$ subsets, then at least one subset must contain at least $\lceil n/m \rceil$ elements. Note that the $\lceil \ \rceil$ enclosing the $n/m$ tells us to round the value up.

The latter version is just a more powerful version, no? It seems strange to me that one version of a theorem can objectively give more information than another, so it's likely that either the latter version is not correct or I am incorrect in thinking that it somehow has more utility.

Or is this normal? Is it common for certain versions of theorems to simply have less utility than other versions?

$\endgroup$
  • 16
    $\begingroup$ It's quite normal, actually, for two slightly different results to be called the same name, and sometimes one of them happens to be slightly stronger than the other (although that's not really the case here). An example (though perhaps not the best) is the fundamental theorem of algebra: it is sometimes stated as "every nonconstant complex polynomial has at least one root" and other times as "every nonconstant complex polynomial of degree $n$ has exactly $n$ roots". The second obviously implies the first, although it's easy to see that the first also implies the second by induction. $\endgroup$ – YiFan Sep 15 at 22:59
30
$\begingroup$

The first version also applies to infinite sets. The latter only applies to finite sets. How can you say the latter is more powerful? It applies to fewer situations.

It is fairly common that a little more information can be extracted from a finite version of a theorem. But that information is frequently useless when applied to the infinite version. For instance, since the cardinality of the real numbers is strictly greater than the cardinality of the integers, there is no injection from the reals to the integers. Using $|\mathbb{R}|$ and $|\mathbb{Z}|$ to represent the cardinalities of the reals and integers, respectively, your second version would say that there are $\lceil |\mathbb{R}|/|\mathbb{Z}| \rceil = |\mathbb{R}|$ reals sent to at least one integer. While true for this pair of infinite sets, this is pretty much useless (thanks, tomasz:) because it can be false for other pairs of infinite sets.

Also, it is not unusual to find there is one easily proved version of a theorem and another difficult to prove version that is a little sharper. The Whitney embedding theorem has a number of sharpenings that are much more difficult to prove.

$\endgroup$
  • 3
    $\begingroup$ Completely forgot about how the latter only applies to finite sets. This was really insightful, thank you! $\endgroup$ – James Ronald Sep 15 at 14:51
  • 18
    $\begingroup$ I feel like even in the infinite case, "in any map from $\mathbb R$ to $\mathbb Z$, there is an integer with at least $|\mathbb R|$ preimages" is still strictly more useful than "there is no injection from $\mathbb R$ to $\mathbb Z$". $\endgroup$ – Misha Lavrov Sep 16 at 1:56
  • $\begingroup$ Why do you think it is "useless information" that continuum many reals are sent to at least one integer? I think it can be quite useful. More importantly, the analogue is not even true for infinite sets. For example, there is a function $f\colon \aleph_\omega\to {\mathbf N}$, such that for every $n$, $\lvert f^{-1}[\{n\}]\times \mathbf N\rvert<\aleph_\omega$ (it is true if the larger cardinal is regular, or at least has cofinality larger than the smaller cardinal --- this is the case for finite cardinals, of course). $\endgroup$ – tomasz Sep 16 at 12:14
  • 3
    $\begingroup$ I've actually used that "useless" strengthening for infinite sets quite a few times. $\endgroup$ – Richard Rast Sep 16 at 12:18
  • 2
    $\begingroup$ @EricTowers: It is not useless when it is actually true. $\endgroup$ – tomasz Sep 16 at 13:15
11
$\begingroup$

Besides the two good answers already present, I would like to mention that the second version is also a trivial corollary of the first: indeed, if you take $m$ disjoint subsets $A_1,\ldots,A_m$ of $A$, each with less than $\lceil n/m\rceil$ elements, then the union $\bigcup_{j=1}^m A_j$ has at most $m\lfloor n/m\rfloor<n$ elements; so by the "simple" Pigeonhole Principle there cannot be an injection $A\to\bigcup_{j=1}^m A_j$.

So, for finite sets, both versions are easily seen to be equivalent. As mentioned, the first one also applies to infinite sets.

$\endgroup$
5
$\begingroup$

This is perfectly normal. If you like, the first version is a corollary of the second one (assuming you are interested in finite sets). It has less utility in the sense that it is less powerful but more utility in the sense that it actually gets applied more often.

$\endgroup$
  • 1
    $\begingroup$ This argument is correct for finite sets. See @EricTowers answer. $\endgroup$ – Ethan Bolker Sep 15 at 14:37
  • 1
    $\begingroup$ @EthanBolker As this problem was tagged as discrete math and combinatorics, it seemed appropriate to answer in a finite context. (And thank you for the edit!) $\endgroup$ – Matthew Daly Sep 15 at 14:38
  • $\begingroup$ That makes sense, I was too narrow in my thinking: thanks! $\endgroup$ – James Ronald Sep 15 at 14:52
1
$\begingroup$

Which version is more useful depends on the situation. There are many situations where all that's needed is one hole with more than one pigeon, and besides that, the number of pigeons in each hole is not important.

As an additional note, for infinite sets, the nature of the principles changes. The definition of cardinality is equivalence classes defined in terms of injectivity, so saying that if |A| > |B| then there's injective function is pretty much just a restatement of the definition. And for infinite sets, if |A| > |B|, then, to the extent that |A|/|B| is defined, it is equal to |A|. For instance, if you assign to each integer a set of real numbers, and each real number is in at least one such set, then at least one set has the same cardinality as the set of real numbers.

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