mdfrbf_fibre_subset
Pigeonhole: if f : Fin d → Fin b and b*n < d, then some fibre of f contains n+1 points; equivalently there are a colour c and a set W of n+1 points on which f is constantly c.
Statement
theorem mdfrbf_fibre_subset {d b : ℕ} (f : Fin d → Fin b) (n : ℕ) (h : b * n < d) :
∃ c : Fin b, ∃ W : Finset (Fin d), W.card = n + 1 ∧ ∀ w ∈ W, f w = c- Source
- step towards mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- mixed_diamond_fan_ramsey_bound_all_singletons_fan_coloursCase b ≥ 2 with every singleton fan-coloured: if d ≥ j*a + (j-1)*b + 1 and the statement holds at (a, b-1) in dimension d-(j-1), then χ…
The proof, explained
By the pigeonhole principle, since $b \cdot n < d$, there is some colour $c \in \mathrm{Fin}(b)$ whose fiber under $f$ has strictly more than $n$ elements. Consequently, this fiber has cardinality at least $n + 1$. Selecting any subset $W$ of $n + 1$ elements from this fiber yields the desired set on which $f$ is identically $c$.
There is an element $c \in \mathrm{Fin}(b)$ whose fiber under $f$ contains strictly more than $n$ elements.
The domain $\mathrm{Fin}(d)$ has cardinality $d$ and the codomain $\mathrm{Fin}(b)$ has cardinality $b$. Given the hypothesis $b \cdot n < d$, the pigeonhole principle (`Fintype.exists_lt_card_fiber_of_mul_lt_card`) implies that some fiber $\{x \mid f(x) = c\}$ contains strictly more than $n$ elements.
uses
Fintype.exists_lt_card_fiber_of_mul_lt_cardclassical obtain ⟨c, hc⟩ := Fintype.exists_lt_card_fiber_of_mul_lt_card f (n := n) (by simpa using h)
The fiber of $c$ contains a subset $W$ of cardinality $n + 1$, completing the proof.
We choose $c$ as the witness colour. Because its fiber has cardinality strictly greater than $n$, the cardinality is at least $n + 1$. By `Finset.exists_subset_card_eq`, any finite set of size at least $n + 1$ contains a subset of size exactly $n + 1$, yielding a subset $W \subseteq \{x \mid f(x) = c\}$ with $|W| = n + 1$. Since every $w \in W$ belongs to the fiber of $c$, $f(w) = c$ holds for all $w \in W$.
uses
Finset.exists_subset_card_eqrefine ⟨c, ?_⟩ have hc' : n + 1 ≤ (Finset.univ.filter (fun x => f x = c)).card := hc obtain ⟨W, hW, hWc⟩ := Finset.exists_subset_card_eq hc' exact ⟨W, hWc, fun w hw => by simpa using hW hw⟩
Fintype.exists_lt_card_fiber_of_mul_lt_card- If a map between finite types satisfies $|\beta| \cdot n < |\alpha|$, then some element of $\beta$ has a fiber with strictly more than $n$ elements.
Finset.exists_subset_card_eq- A finite set of cardinality at least $n$ contains a subset of cardinality exactly $n$.
- Line 4 invokes `classical` to provide decidability instances (such as decidable equality on `Fin b`), a formal requirement for defining fibers as finite sets and applying `Fintype.exists_lt_card_fiber_of_mul_lt_card`.
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 step extracting j-1 = n+1 points sharing one fan colour. -/theorem mdfrbf_fibre_subset {d b : ℕ} (f : Fin d → Fin b) (n : ℕ) (h : b * n < d) : ∃ c : Fin b, ∃ W : Finset (Fin d), W.card = n + 1 ∧ ∀ w ∈ W, f w = c := by classical obtain ⟨c, hc⟩ := Fintype.exists_lt_card_fiber_of_mul_lt_card f (n := n) (by simpa using h) refine ⟨c, ?_⟩ have hc' : n + 1 ≤ (Finset.univ.filter (fun x => f x = c)).card := hc obtain ⟨W, hW, hWc⟩ := Finset.exists_subset_card_eq hc' exact ⟨W, hWc, fun w hw => by simpa using hW hw⟩