Meaning of pigeonhole principle | Babel Free

Definitions

The 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).

countable, uncountable

Equivalents

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.”

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

“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.”

CEFR level