The strong pigeonhole principle
ProvedFamousTheorems.strong_pigeonhole_principleThe strong pigeonhole principle. Let be a map between finite sets and a natural number with . Then some fibre of has more than elements: there is with .
Equivalently, if objects are put into boxes, some box receives at least objects. This is the everyday form of the pigeonhole principle in combinatorics, used for example in the Erdős–Szekeres theorem on monotone subsequences and in Ramsey theory.
Formalization note. Mathlib's Fintype.exists_lt_card_fiber_of_mul_lt_card. The fibre is written as Finset.univ.filter fun x => f x = y.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem strong_pigeonhole_principle {α β : Type*} [Fintype α] [Fintype β] [DecidableEq β] (f : α → β) {n : ℕ}
(hn : Fintype.card β * n < Fintype.card α) : ∃ y : β, n < (Finset.univ.filter fun x => f x = y).card := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Fintype.exists_lt_card_fiber_of_mul_lt_card`. Proof here reduces to that Mathlib result.