pigeonhole principle

plural pigeonhole principles

1. countableuncountablemathematicsThe theorem which states that any partition of a finite set of n elements into m (< 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 the cardinality of the unpartitioned set exceeds that of the partition (so there is no one-to-one correspondence).

   1. κ is a regular cardinal. 2. If we put κ pigeons into λ < κ pigeonholes, then some pigeonhole must contain κ pigeons.

   2009, John Harris, Jeffry L. Hirst, Michael Mossinghoff, Combinatorics and Graph Theory, Springer, page 313, Of course our list of pigeonhole principles is not all inclusive. For example, more set theoretic pigeonhole principles are given in [72]. Corollary 3.31 (Ultimate Pigeonhole Principle). The following are equivalent

   2 more examples

   The pigeonhole principle is usually stated as follows. (16.43) If more than n pigeons are placed in n holes, at least one hole will contain more than one pigeon. The pigeonhole principle is obvious, and one may wonder what it has to do with computer science or mathematics.

   1993, David Gries, Fred B. Schneider, A Logical Approach to Discrete Math, Springer, page 355

   2012, Dov M. Gabbay, Akihiro Kanamori, John Woods (editors), Handbook of the History of Logic: Volume 6: Sets and Extensions in the Twentieth Century, Elevier (North-Holland), page 325, As we turn to look at various pigeonhole 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.

   Synonyms: Dirichlet's box principle, Dirichlet's drawer principle