mdfrbf_fan_of_c_subset
Fan witness from a c-coloured block: if W has j-1 points, each of whose singletons is c-coloured, and B is a nonempty c-coloured subset of a c-coloured set top which contains W and is disjoint from B, then there is a monochromatic F_j in colour c (top, with the j-1 singletons of W plus B as middles).
Statement
theorem mdfrbf_fan_of_c_subset {j d k : ℕ} (hj : 2 ≤ j) (W : Finset (Fin d)) (hW : W.card = j - 1)
(χ : Finset (Fin d) → Fin k) (c : Fin k) (top B : Finset (Fin d))
(hcol : χ top = c) (hWtop : W ⊆ top) (hWc : ∀ w ∈ W, χ {w} = c)
(hBne : B.Nonempty) (hBsub : B ⊆ top) (hBcol : χ B = c) (hBdisj : Disjoint B W) :
has_monochromatic_fan_copy j d c χ- Source
- step towards mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- has_monochromatic_fan_copyFor a colouring χ of the subsets of Fin d with k colours, has_monochromatic_fan_copy j d col χ holds if there is a set top of colour col…
- 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
To construct a monochromatic fan $F_j$ in colour $c$, the proof defines the collection $S$ of middle sets consisting of $B$ together with the $j - 1$ singletons $\{w\}$ for $w \in W$. Since $B$ is nonempty and disjoint from $W$, $B$ cannot be one of these singletons, so $S$ has cardinality exactly $(j - 1) + 1 = j$. Each member of $S$ is shown to be monochromatic of colour $c$ and a proper subset of $\mathrm{top}$, and the disjointness of $B$ and $W$ prevents any inclusion between distinct elements of $S$. Indexing $S$ by $\mathrm{Fin}\, j$ then provides the desired fan copy.
Let $S$ be the family of sets obtained by adding $B$ to the set of singletons $\{\{w\} : w \in W\}$.
We enable classical logic and define the candidate family $S = \{B\} \cup \{\{w\} : w \in W\}$ of middle sets for the fan.
classical let S : Finset (Finset (Fin d)) := insert B (W.image (fun w => ({w} : Finset (Fin d)))) have hSdef : S = insert B (W.image (fun w => ({w} : Finset (Fin d)))) := rfl
$B$ is not among the singletons of elements of $W$.
Suppose for contradiction that $B = \{w\}$ for some $w \in W$. Since $B$ is nonempty, choose an element $b \in B$. Then $b \in \{w\}$, which implies $b = w$. Thus $b \in W$, which contradicts the assumption that $B$ and $W$ are disjoint.
uses
Finset.mem_image.mp,Finset.mem_singleton.mp,Finset.mem_singleton.mpr,Finset.disjoint_left.mphave hBnotmem : B ∉ W.image (fun w => ({w} : Finset (Fin d))) := by intro h obtain ⟨w, hw, hwB⟩ := Finset.mem_image.mp h obtain ⟨b, hbB⟩ := hBne have hbw : b = w := by rw [← hwB] at hbB exact Finset.mem_singleton.mp hbB have hbB' : b ∈ B := by rw [← hwB] exact Finset.mem_singleton.mpr hbw exact (Finset.disjoint_left.mp hBdisj hbB') (hbw ▸ hw)
The family $S$ has cardinality $j$, giving a bijection $e : S \simeq \mathrm{Fin}\, j$.
Because the singleton map $w \mapsto \{w\}$ is injective, the image of $W$ under this map has cardinality $|W| = j - 1$. Since $B$ is not in this image, inserting $B$ yields $|S| = (j - 1) + 1 = j$ by linear arithmetic using $j \ge 2$. Composing the canonical indexing of $S$ with the equality $|S| = j$ yields a bijection $e : S \simeq \mathrm{Fin}\, j$.
uses
Finset.card_image_of_injective,Finset.singleton_inj.mp,Finset.card_insert_of_notMem,Finset.equivFin,finCongrhave hSimgcard : (W.image (fun w => ({w} : Finset (Fin d)))).card = W.card := Finset.card_image_of_injective W (fun a b h => Finset.singleton_inj.mp h) have hScard : S.card = j := by rw [hSdef, Finset.card_insert_of_notMem hBnotmem, hSimgcard, hW] omega let e : ↥S ≃ Fin j := (Finset.equivFin S).trans (finCongr hScard)
$W$ is nonempty.
If $W$ were empty, its cardinality would be 0. But by assumption $|W| = j - 1$ and $j \ge 2$, so $|W| \ge 1 > 0$, a contradiction.
uses
Finset.nonempty_iff_ne_empty,Finset.card_emptyhave hWne : W.Nonempty := by rw [Finset.nonempty_iff_ne_empty] intro h0 rw [h0, Finset.card_empty] at hW omega
Every set $X \in S$ is a subset of $\mathrm{top}$, has colour $c$, and is strictly smaller than $\mathrm{top}$.
Take any $X \in S$, which is either $B$ or $\{w\}$ for some $w \in W$. If $X = B$, we are given $B \subseteq \mathrm{top}$ and $\chi(B) = c$. If $B = \mathrm{top}$, then since $W$ is nonempty, any $w \in W \subseteq \mathrm{top}$ would belong to $B$, violating the disjointness of $B$ and $W$; hence $B \ne \mathrm{top}$. If $X = \{w\}$ for $w \in W$, then $\{w\} \subseteq \mathrm{top}$ (since $w \in W \subseteq \mathrm{top}$) and $\chi(\{w\}) = c$ by assumption. If $\{w\} = \mathrm{top}$, then since $B$ is nonempty, any $b \in B \subseteq \mathrm{top}$ satisfies $b \in \{w\}$, giving $b = w \in W$, which again contradicts $B \cap W = \emptyset$. Thus $\{w\} \ne \mathrm{top}$.
uses
Finset.mem_insert,Finset.disjoint_left.mp,Finset.mem_image.mp,Finset.singleton_subset_iff.mpr,Finset.mem_singleton.mphave hSprop : ∀ X ∈ S, X ⊆ top ∧ χ X = c ∧ X ≠ top := by intro X hX rw [hSdef, Finset.mem_insert] at hX rcases hX with hXB | hX · rw [hXB] refine ⟨hBsub, hBcol, ?_⟩ intro hEq obtain ⟨w, hw⟩ := hWne have hwt : w ∈ top := hWtop hw rw [← hEq] at hwt exact (Finset.disjoint_left.mp hBdisj hwt) hw · obtain ⟨w, hw, hwX⟩ := Finset.mem_image.mp hX rw [← hwX] refine ⟨Finset.singleton_subset_iff.mpr (hWtop hw), hWc w hw, ?_⟩ intro hEq obtain ⟨b, hbB⟩ := hBne have hbt : b ∈ top := hBsub hbB rw [← hEq] at hbt have hbw : b = w := Finset.mem_singleton.mp hbt have hbW : b ∈ W := hbw ▸ hw exact (Finset.disjoint_left.mp hBdisj hbB) hbW
The family $S$ forms an antichain under inclusion: if $X, Y \in S$ and $X \subseteq Y$, then $X = Y$.
Let $X, Y \in S$ with $X \subseteq Y$. If $X = B$, then either $Y = B$ (so $X = Y$), or $Y = \{w\}$ for $w \in W$, in which case $B \subseteq \{w\}$ forces any $b \in B$ to equal $w \in W$, contradicting disjointness. If $X = \{w\}$ for $w \in W$, then either $Y = B$ (so $w \in B$, contradicting disjointness), or $Y = \{w'\}$ for $w' \in W$, in which case $\{w\} \subseteq \{w'\}$ implies $w = w'$ and $X = Y$.
uses
Finset.mem_insert,Finset.mem_image.mp,Finset.mem_singleton.mp,Finset.disjoint_left.mp,Finset.mem_singleton.mprhave hanti : ∀ X ∈ S, ∀ Y ∈ S, X ⊆ Y → X = Y := by intro X hX Y hY hsub rw [hSdef, Finset.mem_insert] at hX hY rcases hX with hXB | hX · rw [hXB] at hsub ⊢ rcases hY with hYB | hY · rw [hYB] · obtain ⟨w, hw, hwY⟩ := Finset.mem_image.mp hY rw [← hwY] at hsub ⊢ exfalso obtain ⟨b, hbB⟩ := hBne have hbw : b = w := Finset.mem_singleton.mp (hsub hbB) exact (Finset.disjoint_left.mp hBdisj hbB) (hbw ▸ hw) · obtain ⟨w, hw, hwX⟩ := Finset.mem_image.mp hX rw [← hwX] at hsub ⊢ rcases hY with hYB | hY · rw [hYB] at hsub ⊢ exfalso have hwB : w ∈ B := hsub (Finset.mem_singleton.mpr rfl) exact (Finset.disjoint_left.mp hBdisj hwB) hw · obtain ⟨w', hw', hwY⟩ := Finset.mem_image.mp hY rw [← hwY] at hsub ⊢ have hww' : w = w' := Finset.mem_singleton.mp (hsub (Finset.mem_singleton.mpr rfl)) rw [hww']
The set $\mathrm{top}$ together with the middle sets $\mathrm{mid}_i = e^{-1}(i)$ form a monochromatic fan of colour $c$.
We witness the fan with $\mathrm{top}$ (which has colour $c$) and the $j$ middle sets $\mathrm{mid}_i = e^{-1}(i) \in S$ for $i \in \mathrm{Fin}\, j$. By Step 5, each $\mathrm{mid}_i$ is a subset of $\mathrm{top}$ not equal to $\mathrm{top}$ (so $\mathrm{mid}_i \subsetneq \mathrm{top}$) and has colour $c$. Furthermore, if $i \ne i'$ but $\mathrm{mid}_i \subseteq \mathrm{mid}_{i'}$, the antichain property of $S$ forces $\mathrm{mid}_i = \mathrm{mid}_{i'}$, which contradicts $i \ne i'$ by injectivity of $e^{-1}$.
uses
Finset.ssubset_iff_subset_ne.mpr,Subtype.extrefine ⟨top, hcol, fun i => ((e.symm i : ↥S) : Finset (Fin d)), ?_, ?_⟩ · intro i have hmem : ((e.symm i : ↥S) : Finset (Fin d)) ∈ S := (e.symm i).2 obtain ⟨hsub, hcolmid, hne⟩ := hSprop _ hmem exact ⟨Finset.ssubset_iff_subset_ne.mpr ⟨hsub, hne⟩, hcolmid⟩ · intro i i' hne hsub exact hne (e.symm.injective (Subtype.ext (hanti _ (e.symm i).2 _ (e.symm i').2 hsub)))
Finset.card_empty- The empty set has cardinality zero ($|\emptyset| = 0$).
Finset.card_image_of_injective- If $f$ is an injective function, then the image of a finite set $s$ under $f$ has the same cardinality as $s$.
Finset.card_insert_of_notMem- Inserting an element $a \notin s$ into a finite set $s$ increases its cardinality by 1.
Finset.disjoint_left.mp- If two sets $A$ and $B$ are disjoint, then any element in $A$ does not belong to $B$.
Finset.equivFin- Any finite set $s$ is in bijection with $\mathrm{Fin}(|s|)$.
Finset.mem_image.mp- An element $y$ belongs to the image of $s$ under $f$ if and only if $y = f(x)$ for some $x \in s$.
Finset.mem_insert- An element belongs to $\mathrm{insert}(a, s)$ if and only if it equals $a$ or belongs to $s$.
Finset.mem_singleton.mp- If $x \in \{a\}$, then $x = a$.
Finset.mem_singleton.mpr- If $x = a$, then $x \in \{a\}$.
Finset.nonempty_iff_ne_empty- A finite set is nonempty if and only if it is not equal to the empty set.
Finset.singleton_inj.mp- If two singletons $\{a\}$ and $\{b\}$ are equal, then $a = b$.
Finset.singleton_subset_iff.mpr- If $a \in s$, then the singleton $\{a\}$ is a subset of $s$.
Finset.ssubset_iff_subset_ne.mpr- If $A \subseteq B$ and $A \ne B$, then $A$ is a strict subset of $B$ ($A \subsetneq B$).
Subtype.ext- Two subtype elements are equal if their underlying carrier values are equal.
finCongr- If $n = m$, then the finite types $\mathrm{Fin}(n)$ and $\mathrm{Fin}(m)$ are naturally equivalent.
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.
/-- Builds the monochromatic fan in colour c out of the j-1 c-coloured singletons of W together with one c-coloured nonempty set B inside the c-coloured top. -/theorem mdfrbf_fan_of_c_subset {j d k : ℕ} (hj : 2 ≤ j) (W : Finset (Fin d)) (hW : W.card = j - 1) (χ : Finset (Fin d) → Fin k) (c : Fin k) (top B : Finset (Fin d)) (hcol : χ top = c) (hWtop : W ⊆ top) (hWc : ∀ w ∈ W, χ {w} = c) (hBne : B.Nonempty) (hBsub : B ⊆ top) (hBcol : χ B = c) (hBdisj : Disjoint B W) : has_monochromatic_fan_copy j d c χ := by classical let S : Finset (Finset (Fin d)) := insert B (W.image (fun w => ({w} : Finset (Fin d)))) have hSdef : S = insert B (W.image (fun w => ({w} : Finset (Fin d)))) := rfl have hBnotmem : B ∉ W.image (fun w => ({w} : Finset (Fin d))) := by intro h obtain ⟨w, hw, hwB⟩ := Finset.mem_image.mp h obtain ⟨b, hbB⟩ := hBne have hbw : b = w := by rw [← hwB] at hbB exact Finset.mem_singleton.mp hbB have hbB' : b ∈ B := by rw [← hwB] exact Finset.mem_singleton.mpr hbw exact (Finset.disjoint_left.mp hBdisj hbB') (hbw ▸ hw) have hSimgcard : (W.image (fun w => ({w} : Finset (Fin d)))).card = W.card := Finset.card_image_of_injective W (fun a b h => Finset.singleton_inj.mp h) have hScard : S.card = j := by rw [hSdef, Finset.card_insert_of_notMem hBnotmem, hSimgcard, hW] omega let e : ↥S ≃ Fin j := (Finset.equivFin S).trans (finCongr hScard) have hWne : W.Nonempty := by rw [Finset.nonempty_iff_ne_empty] intro h0 rw [h0, Finset.card_empty] at hW omega have hSprop : ∀ X ∈ S, X ⊆ top ∧ χ X = c ∧ X ≠ top := by intro X hX rw [hSdef, Finset.mem_insert] at hX rcases hX with hXB | hX · rw [hXB] refine ⟨hBsub, hBcol, ?_⟩ intro hEq obtain ⟨w, hw⟩ := hWne have hwt : w ∈ top := hWtop hw rw [← hEq] at hwt exact (Finset.disjoint_left.mp hBdisj hwt) hw · obtain ⟨w, hw, hwX⟩ := Finset.mem_image.mp hX rw [← hwX] refine ⟨Finset.singleton_subset_iff.mpr (hWtop hw), hWc w hw, ?_⟩ intro hEq obtain ⟨b, hbB⟩ := hBne have hbt : b ∈ top := hBsub hbB rw [← hEq] at hbt have hbw : b = w := Finset.mem_singleton.mp hbt have hbW : b ∈ W := hbw ▸ hw exact (Finset.disjoint_left.mp hBdisj hbB) hbW have hanti : ∀ X ∈ S, ∀ Y ∈ S, X ⊆ Y → X = Y := by intro X hX Y hY hsub rw [hSdef, Finset.mem_insert] at hX hY rcases hX with hXB | hX · rw [hXB] at hsub ⊢ rcases hY with hYB | hY · rw [hYB] · obtain ⟨w, hw, hwY⟩ := Finset.mem_image.mp hY rw [← hwY] at hsub ⊢ exfalso obtain ⟨b, hbB⟩ := hBne have hbw : b = w := Finset.mem_singleton.mp (hsub hbB) exact (Finset.disjoint_left.mp hBdisj hbB) (hbw ▸ hw) · obtain ⟨w, hw, hwX⟩ := Finset.mem_image.mp hX rw [← hwX] at hsub ⊢ rcases hY with hYB | hY · rw [hYB] at hsub ⊢ exfalso have hwB : w ∈ B := hsub (Finset.mem_singleton.mpr rfl) exact (Finset.disjoint_left.mp hBdisj hwB) hw · obtain ⟨w', hw', hwY⟩ := Finset.mem_image.mp hY rw [← hwY] at hsub ⊢ have hww' : w = w' := Finset.mem_singleton.mp (hsub (Finset.mem_singleton.mpr rfl)) rw [hww'] refine ⟨top, hcol, fun i => ((e.symm i : ↥S) : Finset (Fin d)), ?_, ?_⟩ · intro i have hmem : ((e.symm i : ↥S) : Finset (Fin d)) ∈ S := (e.symm i).2 obtain ⟨hsub, hcolmid, hne⟩ := hSprop _ hmem exact ⟨Finset.ssubset_iff_subset_ne.mpr ⟨hsub, hne⟩, hcolmid⟩ · intro i i' hne hsub exact hne (e.symm.injective (Subtype.ext (hanti _ (e.symm i).2 _ (e.symm i').2 hsub)))