---
tag: Z117P4ZE5F
kind: proof
name: Proof of the infinite pigeonhole principle
msc: [05A05]
proves: 0FS3RHF6KE
uses: [01MKW4R283, 0BBTH3YSZA, 0EE2V3CHFK]
sources:
  - url: https://proofwiki.org/wiki/Infinite_Pigeonhole_Principle
---

## Proof

We argue by contradiction.

1. Let $A$ be an [[infinite set|01MKW4R283]], let $B$ be a [[finite set|0BBTH3YSZA]], and let $f : A \to B$ be a function.
2. For $b \in B$, write $A_b = f^{-1}(b) = \set{a \in A : f(a) = b}$.
3. Suppose, for a contradiction, that $A_b$ is finite for every $b \in B$.
4. The sets $A_b$ for $b \in B$ are pairwise disjoint. Indeed, if $a \in A_b \cap A_{b'}$, then $b = f(a) = b'$.
5. Their union is $A$, because each $a \in A$ lies in $A_{f(a)}$.
6. Since $B$ is finite, $A$ is the union of finitely many pairwise disjoint finite sets. If $B$ is empty, this union is empty.
7. By the [[rule of sum|0EE2V3CHFK]], such a union is finite. So $A$ is finite.
8. This contradicts step 1, since an infinite set is by definition not finite.
9. Hence some $b \in B$ has an infinite fibre $f^{-1}(b)$.

## Idea

The fibres of $f$ cover $A$, and there are only finitely many of them. A finite union of finite sets is finite, so one fibre must be infinite.