English Explanatory Dictionary

pigeonhole principle

English dictionary entry

Meanings

noun
  1. 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).

Word forms

pigeonhole principle pigeonhole principles

Etymology

From the commonly used expository example that if n+1 pigeons are placed in n pigeonholes, at least one pigeonhole must contain two (or more) pigeons.

Synonyms

Dirichlet's box principle Dirichlet's drawer principle
This entry uses open data from Wiktionary (CC BY-SA/GFDL). Word forms are used for search and are not indexed as separate pages.
Back to search All on P Russian dictionary Dahl dictionary