mdfrbf_fan_transfer
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
- 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
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.
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.
rintro ⟨top, htopc, mid, hmid, hincomp⟩
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`).
uses
Finset.Subset.antisymm,le_of_eqhave 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))
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.
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_subsethave 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 _)
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`).
uses
Finset.Nonempty.monohave htopne : top.Nonempty := Finset.Nonempty.mono (hmid ⟨0, by omega⟩).1.1 (hmidne ⟨0, by omega⟩)
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.
refine ⟨T top, ?_, fun i => T (mid i), ?_, ?_⟩
χ (T top) = f col.
Since top is nonempty, the colouring preservation hypothesis gives χ (T top) = f (ψ top). Substituting ψ top = col yields f col.
· rw [h top htopne, htopc]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.
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]
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.
· 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.
- The hypothesis that T preserves colour classes under f only applies to nonempty sets A. Consequently, the proof must explicitly establish that the middle sets and the top set are nonempty before rewriting their colours under χ.
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.
/-- 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)