(mathematics) The theorem which states that anypartition of afiniteset ofnelements intom (<n)subsets (allowing empty subsets) must include a subset with two or more elements; any of certain reformulations concerning the partition of infinite sets where thecardinality of the unpartitioned set exceeds that of the partition (so there is no one-to-one correspondence).
1993, David Gries, Fred B. Schneider,A Logical Approach to Discrete Math, Springer,page355:
Thepigeonhole principle is usually stated as follows. (16.43) If more thann pigeons are placed inn holes, at least one hole will contain more than one pigeon. Thepigeonhole principle is obvious, and one may wonder what it has to do with computer science or mathematics.
2009, John Harris, Jeffry L. Hirst, Michael Mossinghoff,Combinatorics and Graph Theory, Springer,page 313,
Of course our list ofpigeonhole principles is not all inclusive. For example, more set theoreticpigeonhole principles are given in [72].
Corollary 3.31 (UltimatePigeonhole Principle).The following are equivalent:
As we turn to look at variouspigeonhole principles and how they are used to prove partition theorems, particularly for pairs, we keep in mind the slogan that is embedded in the Motzkin quote: complete disorder is impossible.
An alternative formulation is thatthecodomain of aninjectivefunction onfinitesets cannot be smaller than itsdomain.With this formulation, no restatement is necessary when infinite sets are considered.
The plural, strictly speaking, refers toformulations of the theorem.
Pigeonhole principle on Wikipedia.Wikipedia