op_258_pigeonhole_blocks
Let s be a finite set and f : α → Fin γ. If γ * k ≤ |s| and γ ≥ 1, then there exists b ∈ Fin γ with |{x ∈ s | f x = b}| ≥ k.
Statement
theorem op_258_pigeonhole_blocks {α : Type*} (s : Finset α) (γ k : ℕ) (hγ : 1 ≤ γ) (f : α → Fin γ) (hs : γ * k ≤ s.card) : ∃ b : Fin γ, k ≤ (s.filter (fun x => f x = b)).card
- Source
- step towards op_258_forces_of_forces_smul_blowup
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- op_258_forces_of_forces_smul_blowupFor γ ≥ 1 and k ≥ 1: if a forces a monochromatic K_{γk}, then the profile γ·a forces a monochromatic K_k.
The proof, explained
The proof applies the pigeonhole principle for finite sets to the map `f : α → Fin γ` targeting the full universe of `Fin γ`. It first confirms the prerequisites: the codomain universe is nonempty because `γ ≥ 1`, and its size times `k` is at most `|s|` because `|Fin γ| = γ` and `γ * k ≤ |s|`. Invoking the library lemma `Finset.exists_le_card_fiber_of_mul_le_card_of_maps_to` then produces the desired element `b ∈ Fin γ` with fiber cardinality at least `k`.
The universe `Finset.univ` on `Fin γ` is nonempty.
A finite set is nonempty if and only if its cardinality is strictly greater than zero (`Finset.card_pos`). Because the universe of `Fin γ` has cardinality `γ` (`Finset.card_fin`), this condition reduces to `0 < γ`, which follows by linear arithmetic (`omega`) from the assumption `1 ≤ γ`.
uses
Finset.card_pos,Finset.card_finhave ht : (Finset.univ : Finset (Fin γ)).Nonempty := by rw [← Finset.card_pos, Finset.card_fin] omega
The product `|Finset.univ| * k` is at most `|s|`.
Substituting the cardinality of `Finset.univ` with `γ` via `Finset.card_fin` reduces the inequality to `γ * k ≤ |s|`, which is directly provided by the hypothesis `hs`.
uses
Finset.card_finhave hmul : (Finset.univ : Finset (Fin γ)).card * k ≤ s.card := by rw [Finset.card_fin] exact hs
There exists `b ∈ Fin γ` such that the fiber `{x ∈ s | f x = b}` has cardinality at least `k`.
By the pigeonhole principle for maps between finite sets (`Finset.exists_le_card_fiber_of_mul_le_card_of_maps_to`), since `f` maps all elements of `s` into `Finset.univ` (using `Finset.mem_univ`), `Finset.univ` is nonempty (`ht`), and `|Finset.univ| * k ≤ |s|` (`hmul`), there must exist a block `b ∈ Fin γ` whose fiber has size at least `k`. Providing this `b` and its fiber bound closes the existential goal.
uses
Finset.exists_le_card_fiber_of_mul_le_card_of_maps_to,Finset.mem_univobtain ⟨b, -, hb⟩ := Finset.exists_le_card_fiber_of_mul_le_card_of_maps_to (fun a _ => Finset.mem_univ (f a)) ht hmul exact ⟨b, hb⟩
Finset.card_pos- A finite set is nonempty if and only if its cardinality is strictly positive.
Finset.card_fin- The universal finite set of `Fin n` has cardinality `n`.
Finset.exists_le_card_fiber_of_mul_le_card_of_maps_to- If a function maps a finite set `s` into a nonempty finite set `t` and `|t| * n ≤ |s|`, then some element of `t` has a fiber in `s` of cardinality at least `n`.
Finset.mem_univ- Every element of a finite type belongs to its universal finite set.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Pigeonhole principle on finsets partitioned into γ classes: if s has cardinality at least γ * k, then some fiber under f : α → Fin γ has cardinality at least k. -/theorem op_258_pigeonhole_blocks {α : Type*} (s : Finset α) (γ k : ℕ) (hγ : 1 ≤ γ) (f : α → Fin γ) (hs : γ * k ≤ s.card) : ∃ b : Fin γ, k ≤ (s.filter (fun x => f x = b)).card := by have ht : (Finset.univ : Finset (Fin γ)).Nonempty := by rw [← Finset.card_pos, Finset.card_fin] omega have hmul : (Finset.univ : Finset (Fin γ)).card * k ≤ s.card := by rw [Finset.card_fin] exact hs obtain ⟨b, -, hb⟩ := Finset.exists_le_card_fiber_of_mul_le_card_of_maps_to (fun a _ => Finset.mem_univ (f a)) ht hmul exact ⟨b, hb⟩