Which version of the Pigeonhole principle is correct? One is far stronger than the other

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.