pigeonhole principle

Hello, you have come here looking for the meaning of the word pigeonhole principle. In DICTIOUS you will not only get to know all the dictionary meanings for the word pigeonhole principle, but we will also tell you about its etymology, its characteristics and you will know how to say pigeonhole principle in singular and plural. Everything you need to know about the word pigeonhole principle you have here. The definition of the word pigeonhole principle will help you to be more precise and correct when speaking or writing your texts. Knowing the definition ofpigeonhole principle, as well as those of other words, enriches your vocabulary and provides you with more and better linguistic resources.

English

An illustration of the pigeonhole principle: with 10 pigeons in 9 pigeonholes, one hole contains two pigeons

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.

Noun

pigeonhole principle (countable and uncountable, plural pigeonhole principles)

  1. (mathematics) 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).
    • 1993, David Gries, Fred B. Schneider, A Logical Approach to Discrete Math, Springer, page 355:
      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.
    • 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 .
      Corollary 3.31 (Ultimate Pigeonhole Principle). The following are equivalent:
      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.

Usage notes

An alternative formulation is that the codomain of an injective function on finite sets cannot be smaller than its domain. With this formulation, no restatement is necessary when infinite sets are considered.

The plural, strictly speaking, refers to formulations of the theorem.

Synonyms

Translations

Further reading

Wikious
Boobota
Sagapedia