AFTD Auto-Formalizing Theoretical Domains

has_monochromatic_fan_copy_colour_injective_nonempty

theoremverified

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

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

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

    lines 6–8

      intro hψ
      unfold has_monochromatic_fan_copy at hψ ⊢
      rcases hψ with ⟨top, htop, mid, hmid, hinc⟩
  2. 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).

    lines 9–15

    uses Finset.not_nonempty_iff_eq_empty, Finset.subset_empty.mp

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

    lines 16–27

    uses Finset.not_nonempty_iff_eq_empty, Fin.ext_iff, Finset.empty_subset

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

    lines 28–31

      refine ⟨top, ?_, mid, ?_, hinc⟩
      · have h1 : ψ top = f (χ top) := h top htop_ne
        rw [h1] at htop
        exact hf htop
  5. 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.

    lines 32–37

      · 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

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