AFTD Auto-Formalizing Theoretical Domains

mdfrbf_fan_transfer

theoremverified

Push-forward of a monochromatic fan along an order embedding of set systems: if j ≥ 2, T is injective, monotone and reflects inclusions, χ (T A) = f (ψ A) on nonempty A, and ψ has a monochromatic F_j in colour col, then χ has a monochromatic F_j in colour f col.

Statement

theorem mdfrbf_fan_transfer {j K d k k' : ℕ} (hj : 2 ≤ j) (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) :
    has_monochromatic_fan_copy j K col ψ → has_monochromatic_fan_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_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 1

The proof, explained

The proof transfers a monochromatic fan copy across the order embedding T by setting the new top element to T top and the new petals to T (mid i). Because the colouring hypothesis χ (T A) = f (ψ A) requires A to be nonempty, the argument first proves that each petal is nonempty (as an empty petal would be contained in any other petal, contradicting incomparability since j ≥ 2), which also implies top is nonempty. Finally, order reflection and injectivity of T ensure that strict inclusions, pairwise incomparabilities, and monochromaticity under colour f col are all preserved.

  1. Let top and (mid i) witness that ψ has a monochromatic fan copy of size j in colour col.

    Unpack the definition of `has_monochromatic_fan_copy`: we obtain a top set with ψ top = col, and j middle sets (mid i) that are strict subsets of top, coloured col, and pairwise incomparable under inclusion.

    line 7

      rintro ⟨top, htopc, mid, hmid, hincomp⟩
  2. T is injective.

    If T A = T A', then T A ⊆ T A' and T A' ⊆ T A. Because T reflects inclusions, A ⊆ A' and A' ⊆ A, so A = A' by antisymmetry of Finset inclusion (`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. Every middle set mid i is nonempty.

    Suppose for contradiction that mid i = ∅. Since j ≥ 2, the set of indices Fin j with i removed has cardinality j - 1 > 0, so there exists another index i' ≠ i. But then mid i = ∅ ⊆ mid i', contradicting the pairwise incomparability of the middle sets.

    lines 10–19

    uses Finset.nonempty_iff_ne_empty, Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_univ, Fintype.card_fin, Finset.card_pos.mp, Finset.mem_erase, Finset.empty_subset

      have hmidne : ∀ i : Fin j, (mid i).Nonempty := by
        intro i
        rw [Finset.nonempty_iff_ne_empty]
        intro h0
        have hpos : 0 < (Finset.univ.erase i).card := by
          rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin]
          omega
        obtain ⟨i', hi'⟩ := Finset.card_pos.mp hpos
        rw [Finset.mem_erase] at hi'
        exact hincomp i i' hi'.1.symm (by rw [h0]; exact Finset.empty_subset _)
  4. The top set is nonempty.

    Since j ≥ 2, index 0 is valid. The middle set mid 0 is nonempty and is a subset of top, so top is nonempty by monotonicity of nonemptiness (`Finset.Nonempty.mono`).

    lines 20–21

    uses Finset.Nonempty.mono

      have htopne : top.Nonempty :=
        Finset.Nonempty.mono (hmid ⟨0, by omega⟩).1.1 (hmidne ⟨0, by omega⟩)
  5. It suffices to show that T top and the family i ↦ T (mid i) satisfy the three properties of a monochromatic fan copy for χ in colour f col.

    We provide T top as the candidate top element and i ↦ T (mid i) as the candidate petals, generating three subgoals: the colour of T top, the strict inclusion and colour of each T (mid i), and the pairwise incomparability of the petals.

    line 22

      refine ⟨T top, ?_, fun i => T (mid i), ?_, ?_⟩
  6. χ (T top) = f col.

    Since top is nonempty, the colouring preservation hypothesis gives χ (T top) = f (ψ top). Substituting ψ top = col yields f col.

    line 23

      · rw [h top htopne, htopc]
  7. For every index i, T (mid i) is a strict subset of T top, and χ (T (mid i)) = f col.

    Strict inclusion is equivalent to inclusion and inequality (`Finset.ssubset_iff_subset_ne`). T (mid i) ⊆ T top holds because mid i ⊆ top and T preserves inclusions. If T (mid i) = T top, injectivity of T would force mid i = top, contradicting mid i ⊂ top. For the colour, since mid i is nonempty, χ (T (mid i)) = f (ψ (mid i)) = f col.

    lines 24–28

    uses Finset.ssubset_iff_subset_ne, le_of_eq

      · intro i
        refine ⟨?_, ?_⟩
        · rw [Finset.ssubset_iff_subset_ne]
          exact ⟨(hT (mid i) top).mpr (hmid i).1.1, fun heq => (hmid i).1.2 (le_of_eq (hinj heq).symm)⟩
        · rw [h (mid i) (hmidne i), (hmid i).2]
  8. For all distinct indices i ≠ i', T (mid i) is not a subset of T (mid i').

    If T (mid i) ⊆ T (mid i'), then because T reflects inclusions, mid i ⊆ mid i', which contradicts the incomparability of the original petals.

    lines 29–30

      · intro i i' hne hincl
        exact hincomp i i' hne ((hT (mid i) (mid i')).mp hincl)
Finset.Subset.antisymm
Two finite sets that are subsets of each other are equal.
le_of_eq
An equality implies the corresponding non-strict inequality (here, set equality implies inclusion).
Finset.nonempty_iff_ne_empty
A finite set is nonempty if and only if it is not equal to the empty set.
Finset.card_erase_of_mem
Removing an element from a finite set that contains it decreases the set's cardinality by 1.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin
The finite type Fin n has cardinality n.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.mem_erase
An element belongs to a finite set with another element erased if and only if it is not equal to the erased element and belongs to the original set.
Finset.empty_subset
The empty set is a subset of every finite set.
Finset.Nonempty.mono
If a subset of a finite set is nonempty, then the set itself is nonempty.
Finset.ssubset_iff_subset_ne
A finite set is a strict subset of another if and only if it is a subset and not equal to it.

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 fan copy across an order embedding T of set systems (colour change f). -/theorem mdfrbf_fan_transfer {j K d k k' : ℕ} (hj : 2 ≤ j) (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) :    has_monochromatic_fan_copy j K col ψ → has_monochromatic_fan_copy j d (f col) χ := by  rintro ⟨top, 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 hmidne : ∀ i : Fin j, (mid i).Nonempty := by    intro i    rw [Finset.nonempty_iff_ne_empty]    intro h0    have hpos : 0 < (Finset.univ.erase i).card := by      rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin]      omega    obtain ⟨i', hi'⟩ := Finset.card_pos.mp hpos    rw [Finset.mem_erase] at hi'    exact hincomp i i' hi'.1.symm (by rw [h0]; exact Finset.empty_subset _)  have htopne : top.Nonempty :=    Finset.Nonempty.mono (hmid ⟨0, by omega⟩).1.1 (hmidne ⟨0, by omega⟩)  refine ⟨T top, ?_, fun i => T (mid i), ?_, ?_⟩  · rw [h top htopne, htopc]  · intro i    refine ⟨?_, ?_⟩    · rw [Finset.ssubset_iff_subset_ne]      exact ⟨(hT (mid i) top).mpr (hmid i).1.1, fun heq => (hmid i).1.2 (le_of_eq (hinj heq).symm)⟩    · rw [h (mid i) (hmidne i), (hmid i).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