AFTD Auto-Formalizing Theoretical Domains

mdfrbf_fan_of_c_subset

theoremverified

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

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.

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

    lines 7–9

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

    lines 10–20

    uses Finset.mem_image.mp, Finset.mem_singleton.mp, Finset.mem_singleton.mpr, Finset.disjoint_left.mp

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

    lines 21–26

    uses Finset.card_image_of_injective, Finset.singleton_inj.mp, Finset.card_insert_of_notMem, Finset.equivFin, finCongr

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

    lines 27–31

    uses Finset.nonempty_iff_ne_empty, Finset.card_empty

      have hWne : W.Nonempty := by
        rw [Finset.nonempty_iff_ne_empty]
        intro h0
        rw [h0, Finset.card_empty] at hW
        omega
  5. 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}$.

    lines 32–52

    uses Finset.mem_insert, Finset.disjoint_left.mp, Finset.mem_image.mp, Finset.singleton_subset_iff.mpr, Finset.mem_singleton.mp

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

    lines 53–76

    uses Finset.mem_insert, Finset.mem_image.mp, Finset.mem_singleton.mp, Finset.disjoint_left.mp, Finset.mem_singleton.mpr

      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']
  7. 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}$.

    lines 77–83

    uses Finset.ssubset_iff_subset_ne.mpr, Subtype.ext

      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)))
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

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