Editing Pigeonhole principle (section)

== Infinite sets ==
{{Citations needed|section|date=February 2025}}

The pigeonhole principle can be extended to [[infinite set]]s by phrasing it in terms of [[cardinal number]]s: if the cardinality of set {{mvar|A}} is greater than the cardinality of set {{mvar|B}}, then there is no injection from {{mvar|A}} to {{mvar|B}}. However, in this form the principle is [[tautology (logic)|tautological]], since the meaning of the statement that the cardinality of set {{mvar|A}} is greater than the cardinality of set {{mvar|B}} is exactly that there is no injective map from {{mvar|A}} to {{mvar|B}}. However, adding at least one element to a finite set is sufficient to ensure that the cardinality increases.

Another way to phrase the pigeonhole principle for finite sets is similar to the principle that finite sets are [[Dedekind finite]]: Let {{mvar|A}} and {{mvar|B}} be finite sets. If there is a surjection from {{mvar|A}} to {{mvar|B}} that is not injective, then no surjection from {{mvar|A}} to {{mvar|B}} is injective. In fact no function of any kind from {{mvar|A}} to {{mvar|B}} is injective. This is not true for infinite sets: Consider the function on the natural numbers that sends 1 and 2 to 1, 3 and 4 to 2, 5 and 6 to 3, and so on.

There is a similar principle for infinite sets: If uncountably many pigeons are stuffed into countably many pigeonholes, there will exist at least one pigeonhole having uncountably many pigeons stuffed into it.

This principle is not a generalization of the pigeonhole principle for finite sets however: It is in general false for finite sets. In technical terms it says that if {{mvar|A}} and {{mvar|B}} are finite sets such that any surjective function from {{mvar|A}} to {{mvar|B}} is not injective, then there exists an element {{mvar|b}} of {{mvar|B}} such that there exists a bijection between the preimage of {{mvar|b}} and {{mvar|A}}. This is a quite different statement, and is absurd for large finite cardinalities.