has_monochromatic_fan_copy_colour_injective_nonempty
For j ≥ 2, if ψ = f ∘ χ on nonempty sets (f injective), then a monochromatic induced F_j in ψ of colour f col yields one in χ of colour col.
Statement
theorem has_monochromatic_fan_copy_colour_injective_nonempty {j d k k' : ℕ} (hj : 2 ≤ j)
(f : Fin k → Fin k') (hf : Function.Injective f) (col : Fin k) (χ : Finset (Fin d) → Fin k)
(ψ : Finset (Fin d) → Fin k') (h : ∀ A, A.Nonempty → ψ A = f (χ A)) :
has_monochromatic_fan_copy j d (f col) ψ → has_monochromatic_fan_copy j d col χ- Source
- step towards mixed_diamond_fan_ramsey_bound
- Verified
- 18 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 2
- mixed_diamond_fan_ramsey_boundFor j ≥ 2, a colouring of the subsets of Fin d with a + b colours contains a monochromatic induced j-diamond in one of the first a…
- 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
The proof transfers a monochromatic fan copy F_j from the colouring ψ to the colouring χ along an injective map f. Because j ≥ 2, neither the root set top (which strictly contains a blade) nor any blade mid i (which cannot be contained in another blade) can be empty. Since all sets in the fan are nonempty, their colours under ψ and χ are related by ψ(A) = f(χ(A)), allowing the injectivity of f to reflect monochromaticity at colour f(col) back to colour col under χ.
We obtain a monochromatic fan copy under ψ consisting of a root set top and j blades mid i.
Assume ψ contains a monochromatic fan copy of colour f(col). Unfolding the definition provides a root set top of colour f(col) and a family of j blades mid i strictly contained in top, each of colour f(col), such that no blade is contained in any other.
intro hψ unfold has_monochromatic_fan_copy at hψ ⊢ rcases hψ with ⟨top, htop, mid, hmid, hinc⟩
The root set top is nonempty.
Suppose for contradiction that top is empty. Since j ≥ 2, the index 0 exists, so blade mid 0 is strictly contained in top. But mid 0 ⊆ top = ∅ forces mid 0 = ∅, contradicting the strict inclusion mid 0 ⊂ top (which requires top ⊈ mid 0).
uses
Finset.not_nonempty_iff_eq_empty,Finset.subset_empty.mphave htop_ne : top.Nonempty := by by_contra hne rw [Finset.not_nonempty_iff_eq_empty] at hne have hsub : mid ⟨0, by omega⟩ ⊆ top := (hmid ⟨0, by omega⟩).1.1 rw [hne] at hsub have heq : mid ⟨0, by omega⟩ = ∅ := Finset.subset_empty.mp hsub exact (hmid ⟨0, by omega⟩).1.2 (by rw [hne, heq])
Every blade mid i is nonempty.
Suppose for contradiction that some blade mid i is empty. Since j ≥ 2, there exists another index i' ≠ i (we can pick i' = 1 if i = 0, and i' = 0 otherwise). But then the empty set mid i is a subset of mid i', contradicting the pairwise incomparability of distinct blades.
uses
Finset.not_nonempty_iff_eq_empty,Fin.ext_iff,Finset.empty_subsethave hmid_ne : ∀ i, (mid i).Nonempty := by intro i by_contra hne rw [Finset.not_nonempty_iff_eq_empty] at hne obtain ⟨i', hi'⟩ : ∃ i' : Fin j, i' ≠ i := by by_cases hi0 : i = ⟨0, by omega⟩ · refine ⟨⟨1, by omega⟩, ?_⟩ rw [hi0] simp [Fin.ext_iff] · exact ⟨⟨0, by omega⟩, fun hh => hi0 hh.symm⟩ have hsub : mid i ⊆ mid i' := by rw [hne]; exact Finset.empty_subset _ exact hinc i i' hi'.symm hsub
The set top and the blades mid i form a candidate fan copy whose root has colour col under χ.
We use the same root top and blades mid i as the fan copy for χ. Because top is nonempty, ψ(top) = f(χ(top)). Since ψ(top) = f(col), the injectivity of f implies χ(top) = col.
refine ⟨top, ?_, mid, ?_, hinc⟩ · have h1 : ψ top = f (χ top) := h top htop_ne rw [h1] at htop exact hf htop
Each blade mid i is strictly contained in top and has colour col under χ, completing the fan copy.
Strict inclusion mid i ⊂ top and pairwise blade incomparability are preserved directly from ψ. Since each mid i is nonempty, ψ(mid i) = f(χ(mid i)). Combining this with ψ(mid i) = f(col) gives f(χ(mid i)) = f(col), which implies χ(mid i) = col by the injectivity of f.
· intro i refine ⟨(hmid i).1, ?_⟩ have h1 : ψ (mid i) = f (χ (mid i)) := h (mid i) (hmid_ne i) have h2 : ψ (mid i) = f col := (hmid i).2 rw [h1] at h2 exact hf h2
Finset.not_nonempty_iff_eq_empty- A finite set is not nonempty if and only if it is empty.
Finset.subset_empty.mp- If a finite set is a subset of the empty set, then it is empty.
Fin.ext_iff- Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finset.empty_subset- The empty set is a subset of any 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.
/-- Fan copies transfer along an injective relabelling of colours that is honest only off the empty set; fan copies use only nonempty sets when j ≥ 2. -/theorem has_monochromatic_fan_copy_colour_injective_nonempty {j d k k' : ℕ} (hj : 2 ≤ j) (f : Fin k → Fin k') (hf : Function.Injective f) (col : Fin k) (χ : Finset (Fin d) → Fin k) (ψ : Finset (Fin d) → Fin k') (h : ∀ A, A.Nonempty → ψ A = f (χ A)) : has_monochromatic_fan_copy j d (f col) ψ → has_monochromatic_fan_copy j d col χ := by intro hψ unfold has_monochromatic_fan_copy at hψ ⊢ rcases hψ with ⟨top, htop, mid, hmid, hinc⟩ have htop_ne : top.Nonempty := by by_contra hne rw [Finset.not_nonempty_iff_eq_empty] at hne have hsub : mid ⟨0, by omega⟩ ⊆ top := (hmid ⟨0, by omega⟩).1.1 rw [hne] at hsub have heq : mid ⟨0, by omega⟩ = ∅ := Finset.subset_empty.mp hsub exact (hmid ⟨0, by omega⟩).1.2 (by rw [hne, heq]) have hmid_ne : ∀ i, (mid i).Nonempty := by intro i by_contra hne rw [Finset.not_nonempty_iff_eq_empty] at hne obtain ⟨i', hi'⟩ : ∃ i' : Fin j, i' ≠ i := by by_cases hi0 : i = ⟨0, by omega⟩ · refine ⟨⟨1, by omega⟩, ?_⟩ rw [hi0] simp [Fin.ext_iff] · exact ⟨⟨0, by omega⟩, fun hh => hi0 hh.symm⟩ have hsub : mid i ⊆ mid i' := by rw [hne]; exact Finset.empty_subset _ exact hinc i i' hi'.symm hsub refine ⟨top, ?_, mid, ?_, hinc⟩ · have h1 : ψ top = f (χ top) := h top htop_ne rw [h1] at htop exact hf htop · intro i refine ⟨(hmid i).1, ?_⟩ have h1 : ψ (mid i) = f (χ (mid i)) := h (mid i) (hmid_ne i) have h2 : ψ (mid i) = f col := (hmid i).2 rw [h1] at h2 exact hf h2