---
tag: 0HGVCWQGY3
kind: statement
role: theorem
name: Pigeonhole principle
msc: [05A05]
uses: [05099E1NMJ]
sources:
  - url: https://en.wikipedia.org/wiki/Pigeonhole_principle
    locator: lead section
same_as:
  wikidata: Q188276
  wikipedia: Pigeonhole principle
---

## Statement

Let $A$ and $B$ be finite sets with $|A| > |B|$, and let $f : A \to B$ be a function.
Then there are elements $a \neq a'$ of $A$ with $f(a) = f(a')$.
In other words, $f$ is not injective.

## Remarks

In the usual image, if $n + 1$ pigeons sit in $n$ holes, then some hole has at least two pigeons.
Example: among any $13$ people, two have their birthdays in the same month.
The [[generalized pigeonhole principle|0BY7GN3449]] gives a fibre with more than $n$ elements. The [[infinite pigeonhole principle|0FS3RHF6KE]] is a version for infinite sets.

## Explanations

### L1 human

If there are more objects than boxes, some box has two objects.
For example, in any group of 367 people, two share a birthday, because a year has at most 366 days.