AFTD Auto-Formalizing Theoretical Domains

has_monochromatic_diamond_copy_colour_injective_nonempty

theoremverified

If ψ = f ∘ χ on nonempty sets (f injective) and ψ ∅ ≠ f col, then a monochromatic induced j-diamond in ψ of colour f col yields one in χ of colour col.

Statement

theorem has_monochromatic_diamond_copy_colour_injective_nonempty {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.Nonempty → ψ A = f (χ A))
    (hempty : ψ ∅ ≠ f col) :
    has_monochromatic_diamond_copy j d (f col) ψ → has_monochromatic_diamond_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_diamond_copyFor a colouring χ of the subsets of Fin d with k colours, has_monochromatic_diamond_copy j d col χ holds if there are sets bot ⊂ top of…
Used by 2

The proof, explained

Given a monochromatic diamond copy of colour f col in ψ, the proof shows that the exact same configuration of sets forms a monochromatic diamond copy of colour col in χ. Because ψ ∅ ≠ f col, the bottom set of the diamond cannot be empty, which implies that the bottom, top, and all middle sets are nonempty. Since ψ = f ∘ χ on nonempty sets and f is injective, every set in the diamond carrying colour f col under ψ must carry colour col under χ.

  1. Let bot, top, and mid be the components of the monochromatic diamond copy for ψ of colour f col.

    We unpack the assumption that ψ contains a monochromatic diamond copy of colour f col. This yields a bottom set bot ⊂ top, both coloured f col by ψ, together with a family of j pairwise incomparable middle sets mid i strictly between bot and top, each also having colour f col under ψ.

    line 7

      rintro ⟨bot, top, hbot_top, hψ_bot, hψ_top, mid, hmid, hmid_inc⟩
  2. The sets bot and top are nonempty.

    If bot were empty, then ψ ∅ = ψ bot = f col, which contradicts the hypothesis hempty that ψ ∅ ≠ f col. Thus bot ≠ ∅, which implies that bot is nonempty by Finset.nonempty_iff_ne_empty.mpr. Because bot ⊂ top, top contains bot and is therefore nonempty as well.

    lines 8–10

    uses Finset.nonempty_iff_ne_empty.mpr

      have hbot_ne : bot ≠ ∅ := fun he => hempty (he ▸ hψ_bot)
      have hbot_nonempty : bot.Nonempty := Finset.nonempty_iff_ne_empty.mpr hbot_ne
      have htop_nonempty : top.Nonempty := hbot_nonempty.mono hbot_top.1
  3. For any nonempty set A, if ψ A = f col, then χ A = col.

    On any nonempty set A, the hypothesis h guarantees ψ A = f (χ A). If ψ A = f col, then f (χ A) = f col, and since f is injective, it follows that χ A = col.

    lines 11–12

      have hcol : ∀ {A}, A.Nonempty → ψ A = f col → χ A = col :=
        fun hA hψ => hf ((h _ hA).symm.trans hψ)
  4. The sets bot, top, and mid satisfy the conditions of a monochromatic diamond copy for χ of colour col, provided each middle set has colour col under χ.

    We provide bot, top, and mid as the witnesses for a diamond copy in χ. The strict inclusion bot ⊂ top and the incomparability of distinct middle sets hold automatically since they depend only on set inclusion, not on the colouring. Since bot and top are nonempty and coloured f col under ψ, the inversion property shows χ bot = col and χ top = col.

    line 13

      refine ⟨bot, top, hbot_top, hcol hbot_nonempty hψ_bot, hcol htop_nonempty hψ_top, mid, fun i => ?_, hmid_inc⟩
  5. Each middle set mid i strictly lies between bot and top and has colour col under χ, completing the proof.

    For each index i, we unpack the given inclusions bot ⊂ mid i and mid i ⊂ top, along with ψ (mid i) = f col. Because bot ⊂ mid i and bot is nonempty, mid i is nonempty. Applying the inversion property yields χ (mid i) = col.

    lines 14–15

      obtain ⟨h1, h2, h3⟩ := hmid i
      exact ⟨h1, h2, hcol (hbot_nonempty.mono h1.1) h3⟩
Finset.nonempty_iff_ne_empty.mpr
A finite set is nonempty if it is not equal to the empty 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

/-- Diamond copies transfer along an injective relabelling of colours that is honest only off the empty set, given that the empty set carries a different colour. -/theorem has_monochromatic_diamond_copy_colour_injective_nonempty {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.Nonempty → ψ A = f (χ A))    (hempty : ψ ∅ ≠ f col) :    has_monochromatic_diamond_copy j d (f col) ψ → has_monochromatic_diamond_copy j d col χ := by  rintro ⟨bot, top, hbot_top, hψ_bot, hψ_top, mid, hmid, hmid_inc⟩  have hbot_ne : bot ≠ ∅ := fun he => hempty (he ▸ hψ_bot)  have hbot_nonempty : bot.Nonempty := Finset.nonempty_iff_ne_empty.mpr hbot_ne  have htop_nonempty : top.Nonempty := hbot_nonempty.mono hbot_top.1  have hcol : ∀ {A}, A.Nonempty → ψ A = f col → χ A = col :=    fun hA hψ => hf ((h _ hA).symm.trans hψ)  refine ⟨bot, top, hbot_top, hcol hbot_nonempty hψ_bot, hcol htop_nonempty hψ_top, mid, fun i => ?_, hmid_inc⟩  obtain ⟨h1, h2, h3⟩ := hmid i  exact ⟨h1, h2, hcol (hbot_nonempty.mono h1.1) h3⟩
See it in the graphDiscuss this resultChallenge it