has_monochromatic_diamond_copy_colour_injective_nonempty
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
- 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
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 χ.
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 ψ.
rintro ⟨bot, top, hbot_top, hψ_bot, hψ_top, mid, hmid, hmid_inc⟩
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.
uses
Finset.nonempty_iff_ne_empty.mprhave 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
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.
have hcol : ∀ {A}, A.Nonempty → ψ A = f col → χ A = col := fun hA hψ => hf ((h _ hA).symm.trans hψ)
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.
refine ⟨bot, top, hbot_top, hcol hbot_nonempty hψ_bot, hcol htop_nonempty hψ_top, mid, fun i => ?_, hmid_inc⟩
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.
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
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.
/-- 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⟩