AFTD Auto-Formalizing Theoretical Domains

mdfrbf_diamond_transfer

theoremverified

Push-forward of a monochromatic diamond along an order embedding of set systems: if T is injective, monotone and reflects inclusions on finsets, χ (T A) = f (ψ A) for every nonempty A, ψ ∅ ≠ col, and ψ has a monochromatic j-diamond in colour col, then χ has a monochromatic j-diamond in colour f col.

Statement

theorem mdfrbf_diamond_transfer {j K d k k' : ℕ} (f : Fin k → Fin k')
    (T : Finset (Fin K) → Finset (Fin d)) (hT : ∀ A A', T A ⊆ T A' ↔ A ⊆ A')
    (χ : Finset (Fin d) → Fin k') (ψ : Finset (Fin K) → Fin k)
    (h : ∀ A, A.Nonempty → χ (T A) = f (ψ A)) (col : Fin k) (hempty : ψ ∅ ≠ col) :
    has_monochromatic_diamond_copy j K col ψ → has_monochromatic_diamond_copy j d (f col) χ
Source
step towards mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours
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 1

The proof, explained

To transfer a monochromatic diamond from ψ to χ along the mapping T, we push forward each set in the diamond by T. Because T reflects inclusions, it is injective and preserves both strict inclusions and incomparability. Since the empty set does not have colour col, every set in the original diamond is nonempty, allowing the transfer hypothesis χ (T A) = f (ψ A) to colour all image sets f col.

  1. Assume the existence of a monochromatic j-diamond for ψ in colour col.

    By assumption, ψ contains a monochromatic diamond copy in colour col, giving bottom and top sets bot ⊂ top with ψ bot = col and ψ top = col, and j middle sets mid i strictly between bot and top, all with ψ (mid i) = col and pairwise incomparable.

    line 7

      rintro ⟨bot, top, hbot, hbotc, htopc, mid, hmid, hincomp⟩
  2. The mapping T is injective.

    If T A = T A', then T A ⊆ T A' and T A' ⊆ T A by le_of_eq. Since T reflects inclusions via hT, this implies A ⊆ A' and A' ⊆ A, hence A = A' by Finset.Subset.antisymm.

    lines 8–9

    uses Finset.Subset.antisymm, le_of_eq

      have hinj : Function.Injective T := fun A A' hh =>
        Finset.Subset.antisymm ((hT A A').mp (le_of_eq hh)) ((hT A' A).mp (le_of_eq hh.symm))
  3. The sets bot, top, and every mid i are nonempty.

    If bot were empty, then ψ ∅ = ψ bot = col, contradicting hempty (ψ ∅ ≠ col); thus bot is nonempty by Finset.nonempty_iff_ne_empty. Since bot ⊂ top, top is also nonempty. Similarly, if any mid i were empty, its colour ψ (mid i) = col would contradict hempty, so every mid i is nonempty.

    lines 10–22

    uses Finset.nonempty_iff_ne_empty

      have hbotne : bot.Nonempty := by
        rw [Finset.nonempty_iff_ne_empty]
        intro h0
        rw [h0] at hbotc
        exact hempty hbotc
      have htopne : top.Nonempty := hbotne.mono hbot.1
      have hmidne : ∀ i : Fin j, (mid i).Nonempty := by
        intro i
        rw [Finset.nonempty_iff_ne_empty]
        intro h0
        have hc := (hmid i).2.2
        rw [h0] at hc
        exact hempty hc
  4. The candidate diamond for χ is given by T bot, T top, and T (mid i).

    We provide the images under T as witnesses for the existential quantifier defining a monochromatic diamond copy for χ: bottom T bot, top T top, and middle sets i ↦ T (mid i).

    line 23

      refine ⟨T bot, T top, ?_, ?_, ?_, fun i => T (mid i), ?_, ?_⟩
  5. T bot ⊂ T top and both sets are coloured f col under χ.

    Using Finset.ssubset_iff_subset_ne, T bot ⊂ T top requires inclusion and inequality: inclusion follows from bot ⊆ top by hT, and equality would imply bot = top by injectivity of T (via le_of_eq), contradicting bot ⊂ top. Because bot and top are nonempty, hypothesis h applies to give χ (T bot) = f (ψ bot) = f col and χ (T top) = f (ψ top) = f col.

    lines 24–27

    uses Finset.ssubset_iff_subset_ne, le_of_eq

      · rw [Finset.ssubset_iff_subset_ne]
        exact ⟨(hT bot top).mpr hbot.1, fun heq => hbot.2 (le_of_eq (hinj heq).symm)⟩
      · rw [h bot hbotne, hbotc]
      · rw [h top htopne, htopc]
  6. Each T (mid i) strictly lies between T bot and T top, with colour f col under χ.

    By Finset.ssubset_iff_subset_ne, the order preservation and reflection hT together with the injectivity of T (via le_of_eq) ensure that bot ⊂ mid i ⊂ top pushes forward to T bot ⊂ T (mid i) ⊂ T top. Nonemptiness of mid i then lets hypothesis h evaluate χ (T (mid i)) = f (ψ (mid i)) = f col.

    lines 28–34

    uses Finset.ssubset_iff_subset_ne, le_of_eq

      · intro i
        refine ⟨?_, ?_, ?_⟩
        · rw [Finset.ssubset_iff_subset_ne]
          exact ⟨(hT bot (mid i)).mpr (hmid i).1.1, fun heq => (hmid i).1.2 (le_of_eq (hinj heq).symm)⟩
        · rw [Finset.ssubset_iff_subset_ne]
          exact ⟨(hT (mid i) top).mpr (hmid i).2.1.1, fun heq => (hmid i).2.1.2 (le_of_eq (hinj heq).symm)⟩
        · rw [h (mid i) (hmidne i), (hmid i).2.2]
  7. For distinct indices i ≠ i', the image sets T (mid i) are incomparable.

    If T (mid i) ⊆ T (mid i'), then order reflection hT would give mid i ⊆ mid i', contradicting the incomparability of the original middle elements mid i and mid i'.

    lines 35–36

      · intro i i' hne hincl
        exact hincomp i i' hne ((hT (mid i) (mid i')).mp hincl)
Finset.Subset.antisymm
If two finite sets are subsets of each other, they are equal.
le_of_eq
Equality implies the preorder relation (here, subset inclusion).
Finset.nonempty_iff_ne_empty
A finite set is nonempty if and only if it is not equal to the empty set.
Finset.ssubset_iff_subset_ne
A finite set is a strict subset of another if and only if it is a subset and the two sets are distinct.

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

/-- Transfers a monochromatic diamond copy across an order embedding T of set systems (colour change f). -/theorem mdfrbf_diamond_transfer {j K d k k' : ℕ} (f : Fin k → Fin k')    (T : Finset (Fin K) → Finset (Fin d)) (hT : ∀ A A', T A ⊆ T A' ↔ A ⊆ A')    (χ : Finset (Fin d) → Fin k') (ψ : Finset (Fin K) → Fin k)    (h : ∀ A, A.Nonempty → χ (T A) = f (ψ A)) (col : Fin k) (hempty : ψ ∅ ≠ col) :    has_monochromatic_diamond_copy j K col ψ → has_monochromatic_diamond_copy j d (f col) χ := by  rintro ⟨bot, top, hbot, hbotc, htopc, mid, hmid, hincomp⟩  have hinj : Function.Injective T := fun A A' hh =>    Finset.Subset.antisymm ((hT A A').mp (le_of_eq hh)) ((hT A' A).mp (le_of_eq hh.symm))  have hbotne : bot.Nonempty := by    rw [Finset.nonempty_iff_ne_empty]    intro h0    rw [h0] at hbotc    exact hempty hbotc  have htopne : top.Nonempty := hbotne.mono hbot.1  have hmidne : ∀ i : Fin j, (mid i).Nonempty := by    intro i    rw [Finset.nonempty_iff_ne_empty]    intro h0    have hc := (hmid i).2.2    rw [h0] at hc    exact hempty hc  refine ⟨T bot, T top, ?_, ?_, ?_, fun i => T (mid i), ?_, ?_⟩  · rw [Finset.ssubset_iff_subset_ne]    exact ⟨(hT bot top).mpr hbot.1, fun heq => hbot.2 (le_of_eq (hinj heq).symm)⟩  · rw [h bot hbotne, hbotc]  · rw [h top htopne, htopc]  · intro i    refine ⟨?_, ?_, ?_⟩    · rw [Finset.ssubset_iff_subset_ne]      exact ⟨(hT bot (mid i)).mpr (hmid i).1.1, fun heq => (hmid i).1.2 (le_of_eq (hinj heq).symm)⟩    · rw [Finset.ssubset_iff_subset_ne]      exact ⟨(hT (mid i) top).mpr (hmid i).2.1.1, fun heq => (hmid i).2.1.2 (le_of_eq (hinj heq).symm)⟩    · rw [h (mid i) (hmidne i), (hmid i).2.2]  · intro i i' hne hincl    exact hincomp i i' hne ((hT (mid i) (mid i')).mp hincl)
See it in the graphDiscuss this resultChallenge it