AFTD Auto-Formalizing Theoretical Domains

has_monochromatic_fan_copy_colour_injective

theoremverified

Relabelling colours by an injective map does not change the existence of a monochromatic induced F_j: if ψ = f ∘ χ with f injective, then χ has a mono F_j in colour col iff ψ has one in colour f col.

Statement

theorem has_monochromatic_fan_copy_colour_injective {j d k k' : ℕ} (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 = 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 3

The proof, explained

A monochromatic fan copy consists of a top vertex and a family of pairwise incomparable petals strictly contained in it, all sharing the same colour. Because containment and incomparability depend solely on the vertices and not on the colouring, any configuration witnessing a fan copy under one colouring serves as the witness under the other. Injectivity of f allows pulling back the colour equalities from f col under ψ to col under χ, while the converse holds by evaluating f on the colours assigned by χ.

  1. The equivalence between the existence of monochromatic fan copies under ψ and χ reduces to proving both directions separately.

    Unfolding the definition of a monochromatic fan copy, the goal is to show that there exist a top vertex and a family of pairwise incomparable petals strictly contained in it, all of a given colour. The if-and-only-if statement is then split into the forward and backward implications.

    lines 6–7

      unfold has_monochromatic_fan_copy
      constructor
  2. If ψ has a monochromatic fan copy of colour f col, then χ has one of colour col.

    Given a fan copy under ψ with top vertex `top` and petals `mid`, we take the exact same sets as the witness for χ. The strict containment `mid i ⊂ top` and pairwise incomparability of the petals are purely set-theoretic properties, so they carry over unchanged. For the colour conditions, the assumption ψ(A) = f(χ(A)) turns ψ(top) = f col into f(χ(top)) = f col, which by injectivity of f implies χ(top) = col. Applying the same argument to each petal gives f(χ(mid i)) = ψ(mid i) = f col, and injectivity of f yields χ(mid i) = col.

    lines 8–12

      · rintro ⟨top, htop, mid, hmid, hinc⟩
        refine ⟨top, hf ?_, mid, ?_, hinc⟩
        · rw [h top] at htop; exact htop
        · intro i
          exact ⟨(hmid i).1, hf (by rw [← h (mid i)]; exact (hmid i).2)⟩
  3. If χ has a monochromatic fan copy of colour col, then ψ has one of colour f col.

    Conversely, given a monochromatic fan copy (top, mid) of colour col under χ, the same sets serve as the witness for ψ. The inclusion and incomparability conditions hold as before. The colour conditions follow directly by substitution: ψ(top) = f(χ(top)) = f col, and for each petal, ψ(mid i) = f(χ(mid i)) = f col.

    lines 13–17

      · rintro ⟨top, htop, mid, hmid, hinc⟩
        refine ⟨top, ?_, mid, ?_, hinc⟩
        · rw [h top, htop]
        · intro i
          exact ⟨(hmid i).1, by rw [h (mid i), (hmid i).2]⟩

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 the colour type. -/theorem has_monochromatic_fan_copy_colour_injective {j d k k' : ℕ} (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 = f (χ A)) :    has_monochromatic_fan_copy j d (f col) ψ ↔ has_monochromatic_fan_copy j d col χ := by  unfold has_monochromatic_fan_copy  constructor  · rintro ⟨top, htop, mid, hmid, hinc⟩    refine ⟨top, hf ?_, mid, ?_, hinc⟩    · rw [h top] at htop; exact htop    · intro i      exact ⟨(hmid i).1, hf (by rw [← h (mid i)]; exact (hmid i).2)⟩  · rintro ⟨top, htop, mid, hmid, hinc⟩    refine ⟨top, ?_, mid, ?_, hinc⟩    · rw [h top, htop]    · intro i      exact ⟨(hmid i).1, by rw [h (mid i), (hmid i).2]⟩
See it in the graphDiscuss this resultChallenge it