The infinite pigeonhole principle
ProvedFamousTheorems.infinite_pigeonhole_principle_cardinalThe infinite pigeonhole principle. Let , where is infinite and . Then some fibre has the full cardinality .
When more than pigeons go into holes, the finite pigeonhole principle only guarantees two pigeons in one hole. For infinite cardinals the cofinality condition gives a hole holding as many pigeons as there are in total. For example, any map from to a finite set has an infinite fibre, and any map from to has an uncountable fibre.
Formalization note. Mathlib's Cardinal.infinite_pigeonhole. Cardinal.mk β is , and (Cardinal.mk β).ord.cof is the cofinality of the initial ordinal of . The two types live in the same universe.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
universe u
theorem infinite_pigeonhole_principle_cardinal {α β : Type u} (f : β → α) (hβ : Cardinal.aleph0 ≤ Cardinal.mk β)
(hα : Cardinal.mk α < (Cardinal.mk β).ord.cof) :
∃ a : α, Cardinal.mk (f ⁻¹' {a}) = Cardinal.mk β := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Cardinal.infinite_pigeonhole`. Proof here reduces to that Mathlib result.