---
tag: 0FS3RHF6KE
kind: statement
role: theorem
name: Infinite pigeonhole principle
msc: [05A05]
uses: [0HGVCWQGY3]
sources:
  - url: https://en.wikipedia.org/wiki/Pigeonhole_principle
    locator: Infinite sets
---

## Statement

Let $A$ be an infinite set, let $B$ be a finite set, and let $f : A \to B$ be a function.
Then there is an element $b \in B$ such that the fibre $f^{-1}(b)$ is infinite.

## Remarks

The proof is short. If each of the finitely many fibres were finite, then $A$, their union, would be finite.
Example: in any infinite sequence of integers, infinitely many terms have the same remainder modulo $10$.
The statement is the starting point of the infinite form of [[Ramsey's theorem|00TQV3F5S4]].

## Explanations

### L1 human

If you put infinitely many objects into finitely many boxes, at least one box gets infinitely many of them.
For example, colour each natural number red or blue. Then one of the two colours is used infinitely often.