AFTD Auto-Formalizing Theoretical Domains

mdfrbf_fibre_subset

theoremverified

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

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$.

  1. 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.

    lines 4–5

    uses Fintype.exists_lt_card_fiber_of_mul_lt_card

      classical
      obtain ⟨c, hc⟩ := Fintype.exists_lt_card_fiber_of_mul_lt_card f (n := n) (by simpa using h)
  2. 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$.

    lines 6–9

    uses Finset.exists_subset_card_eq

      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⟩
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$.

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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it