five_diamond_copy_of_monochromatic_level
If level m is monochromatic of color col and there exist B ⊆ T of color col with |B| + 2 = m = |T| - 2, then there exist 5 middle sets forming an induced monochromatic 5-diamond copy.
Statement
theorem five_diamond_copy_of_monochromatic_level
(d k : ℕ) (c : Finset (Fin d) → Fin k) (col : Fin k) (m : ℕ)
(h_level : ∀ A : Finset (Fin d), A.card = m → c A = col)
(B T : Finset (Fin d)) (hB : c B = col) (hT : c T = col)
(hBT : B ⊆ T) (hB_card : B.card + 2 = m) (hT_card : T.card = m + 2) :
∃ (M : Fin 5 → Finset (Fin d)),
c B = col ∧ c T = col ∧
(∀ i, c (M i) = col) ∧
B ⊂ T ∧
(∀ i, B ⊂ M i ∧ M i ⊂ T) ∧
(∀ i i', i ≠ i' → ¬ (M i ⊆ M i'))- Source
- step towards five_diamond_ramsey_property_at_four_mul
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem constructs an induced monochromatic 5-diamond copy when rank m of the Boolean lattice is monochromatic of color col and there exist monochromatic endpoints B ⊆ T with |B| = m - 2 and |T| = m + 2. The difference T \ B has size 4 and therefore contains Nat.choose 4 2 = 6 two-element subsets, from which a subfamily of 5 subsets e₀, ..., e₄ is chosen. Setting M(i) = B ∪ e(i) gives 5 middle sets of size m (hence monochromatic of color col) strictly between B and T that are pairwise incomparable because recovering e(i) from M(i) \ B ensures distinct indices yield distinct incomparable sets.
|T \ B| = 4
Since B ⊆ T, the size of the set difference is |T \ B| = |T| - |B| by Finset.card_sdiff_of_subset. Using the given sizes |B| + 2 = m and |T| = m + 2, linear integer arithmetic (omega) simplifies (m + 2) - (m - 2) to 4.
uses
Finset.card_sdiff_of_subsethave hTB_card : (T \ B).card = 4 := by have := Finset.card_sdiff_of_subset hBT omega
The set T \ B has 6 two-element subsets
By Finset.card_powersetCard, the number of 2-element subsets of T \ B equals Nat.choose |T \ B| 2. Since |T \ B| = 4, this is Nat.choose 4 2, which evaluates by definition (rfl) to 6.
uses
Finset.card_powersetCardhave hP_card : ((T \ B).powersetCard 2).card = 6 := by rw [Finset.card_powersetCard, hTB_card] rfl
There exists a collection s of 5 two-element subsets of T \ B
By Finset.exists_subset_card_eq, any finite set of size at least 5 has a subset of size 5. Since 5 ≤ 6 (verified by omega), such a 5-element subfamily s exists.
uses
Finset.exists_subset_card_eqobtain ⟨s, hs_sub, hs_card⟩ : ∃ s ⊆ (T \ B).powersetCard 2, s.card = 5 := by apply Finset.exists_subset_card_eq omega
Bijectively index s as e₀, ..., e₄ and define middle sets Mᵢ = B ∪ eᵢ, each of size m
Using Finset.equivFinOfCardEq, s is put in bijection with Fin 5, naming the 2-element subsets e(i). For each index i, we set M(i) = B ∪ e(i). Since e(i) ⊆ T \ B, it is disjoint from B. Because |e(i)| = 2, Finset.card_union_of_disjoint shows |M(i)| = |B| + 2 = m.
uses
Finset.equivFinOfCardEq,Finset.card_union_of_disjointlet e := (Finset.equivFinOfCardEq hs_card).symm let M : Fin 5 → Finset (Fin d) := fun i => B ∪ (e i).val have h_mem (i : Fin 5) : (e i).val ∈ (T \ B).powersetCard 2 := hs_sub (e i).2 have h_sub (i : Fin 5) : (e i).val ⊆ T \ B := (Finset.mem_powersetCard.mp (h_mem i)).1 have h_disj (i : Fin 5) : Disjoint B (e i).val := Finset.disjoint_sdiff.mono_right (h_sub i) have h_card_ei (i : Fin 5) : ((e i).val).card = 2 := (Finset.mem_powersetCard.mp (h_mem i)).2 have hM_card (i : Fin 5) : (M i).card = m := by show (B ∪ (e i).val).card = m rw [Finset.card_union_of_disjoint (h_disj i), h_card_ei i] omega
B is a strict subset of T (B ⊂ T)
By Finset.ssubset_iff_subset_ne, B ⊂ T is equivalent to B ⊆ T and B ≠ T. The inclusion B ⊆ T is given, and B = T is ruled out because their cardinalities m - 2 and m + 2 differ (closed by omega).
uses
Finset.ssubset_iff_subset_nehave hBT_ssub : B ⊂ T := by rw [Finset.ssubset_iff_subset_ne] exact ⟨hBT, by rintro rfl; omega⟩
The family M provides the witness, and every M(i) has color col
We provide M as the candidate family. The top and bottom sets have color col by hypothesis. Since each |M(i)| = m, monochromaticity of level m (h_level) implies c(M(i)) = col. It remains to check the strict inclusions B ⊂ M(i) ⊂ T and incomparability.
refine ⟨M, hB, hT, fun i => h_level (M i) (hM_card i), hBT_ssub, ?_, ?_⟩
For every i, B ⊂ M(i) and M(i) ⊂ T
For any index i: first, B ⊆ M(i) = B ∪ e(i) by Finset.subset_union_left, and equality would force |M(i)| = |B|, contradicting |M(i)| = m = |B| + 2. Second, any element of M(i) belongs to B ⊆ T or to e(i) ⊆ T \ B ⊆ T, so M(i) ⊆ T; equality would force |M(i)| = |T|, contradicting m = m + 2. Both strict inclusions follow by Finset.ssubset_iff_subset_ne.
uses
Finset.ssubset_iff_subset_ne,Finset.subset_union_left· intro i have hMi := hM_card i refine ⟨?_, ?_⟩ · rw [Finset.ssubset_iff_subset_ne] refine ⟨Finset.subset_union_left, ?_⟩ rintro h have : (M i).card = B.card := by rw [← h] omega · rw [Finset.ssubset_iff_subset_ne] refine ⟨?_, ?_⟩ · intro x hx have hx' : x ∈ B ∪ (e i).val := hx rcases Finset.mem_union.mp hx' with hxB | hx_ei · exact hBT hxB · have := h_sub i hx_ei exact (Finset.mem_sdiff.mp this).1 · rintro h have : (M i).card = T.card := by rw [h] omega
Distinct middle sets are incomparable (if i ≠ i', then M(i) ⊈ M(i'))
Suppose i ≠ i' but M(i) ⊆ M(i'). Since |M(i)| = |M(i')| = m, Finset.eq_of_subset_of_card_le implies M(i) = M(i'). Subtracting B from both sides and simplifying via Finset.union_sdiff_cancel_left (using disjointness of B and the 2-sets) yields e(i) = e(i'). Subtype.ext then equates the elements of s, and injectivity of the indexing bijection e forces i = i', a contradiction.
uses
Finset.eq_of_subset_of_card_le,Finset.union_sdiff_cancel_left,Subtype.ext· intro i i' hne hsub have heq : M i = M i' := Finset.eq_of_subset_of_card_le hsub (by rw [hM_card, hM_card]) have h_cancel : ((B ∪ (e i).val) \ B) = ((B ∪ (e i').val) \ B) := by change (M i \ B) = (M i' \ B) rw [heq] rw [Finset.union_sdiff_cancel_left (h_disj i), Finset.union_sdiff_cancel_left (h_disj i')] at h_cancel have he_eq : e i = e i' := Subtype.ext h_cancel have hi_eq : i = i' := e.injective he_eq exact hne hi_eq
Finset.card_sdiff_of_subset- For finite sets s ⊆ t, the cardinality of the difference t \ s is |t| - |s|.
Finset.card_powersetCard- The number of n-element subsets of a finite set s is given by the binomial coefficient |s| choose n.
Finset.exists_subset_card_eq- If n ≤ |s| for a finite set s, then there exists a subset of s of cardinality n.
Finset.equivFinOfCardEq- A finite set of cardinality n is in bijection with Fin n (the standard n-element set {0, ..., n-1}).
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.ssubset_iff_subset_ne- A set s is a strict subset of t if and only if s ⊆ t and s ≠ t.
Finset.subset_union_left- A set s₁ is a subset of the union s₁ ∪ s₂.
Finset.eq_of_subset_of_card_le- If s ⊆ t and |t| ≤ |s| for finite sets, then s = t.
Finset.union_sdiff_cancel_left- If s and t are disjoint finite sets, then (s ∪ t) \ s = t.
Subtype.ext- Two subtype elements are equal if their underlying values are equal.
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.
/-- If level m is monochromatic of color col and there exist B ⊆ T of color col with |B| + 2 = m = |T| - 2, then there exist 5 middle sets forming an induced monochromatic 5-diamond copy. -/theorem five_diamond_copy_of_monochromatic_level (d k : ℕ) (c : Finset (Fin d) → Fin k) (col : Fin k) (m : ℕ) (h_level : ∀ A : Finset (Fin d), A.card = m → c A = col) (B T : Finset (Fin d)) (hB : c B = col) (hT : c T = col) (hBT : B ⊆ T) (hB_card : B.card + 2 = m) (hT_card : T.card = m + 2) : ∃ (M : Fin 5 → Finset (Fin d)), c B = col ∧ c T = col ∧ (∀ i, c (M i) = col) ∧ B ⊂ T ∧ (∀ i, B ⊂ M i ∧ M i ⊂ T) ∧ (∀ i i', i ≠ i' → ¬ (M i ⊆ M i')) := by have hTB_card : (T \ B).card = 4 := by have := Finset.card_sdiff_of_subset hBT omega have hP_card : ((T \ B).powersetCard 2).card = 6 := by rw [Finset.card_powersetCard, hTB_card] rfl obtain ⟨s, hs_sub, hs_card⟩ : ∃ s ⊆ (T \ B).powersetCard 2, s.card = 5 := by apply Finset.exists_subset_card_eq omega let e := (Finset.equivFinOfCardEq hs_card).symm let M : Fin 5 → Finset (Fin d) := fun i => B ∪ (e i).val have h_mem (i : Fin 5) : (e i).val ∈ (T \ B).powersetCard 2 := hs_sub (e i).2 have h_sub (i : Fin 5) : (e i).val ⊆ T \ B := (Finset.mem_powersetCard.mp (h_mem i)).1 have h_disj (i : Fin 5) : Disjoint B (e i).val := Finset.disjoint_sdiff.mono_right (h_sub i) have h_card_ei (i : Fin 5) : ((e i).val).card = 2 := (Finset.mem_powersetCard.mp (h_mem i)).2 have hM_card (i : Fin 5) : (M i).card = m := by show (B ∪ (e i).val).card = m rw [Finset.card_union_of_disjoint (h_disj i), h_card_ei i] omega have hBT_ssub : B ⊂ T := by rw [Finset.ssubset_iff_subset_ne] exact ⟨hBT, by rintro rfl; omega⟩ refine ⟨M, hB, hT, fun i => h_level (M i) (hM_card i), hBT_ssub, ?_, ?_⟩ · intro i have hMi := hM_card i refine ⟨?_, ?_⟩ · rw [Finset.ssubset_iff_subset_ne] refine ⟨Finset.subset_union_left, ?_⟩ rintro h have : (M i).card = B.card := by rw [← h] omega · rw [Finset.ssubset_iff_subset_ne] refine ⟨?_, ?_⟩ · intro x hx have hx' : x ∈ B ∪ (e i).val := hx rcases Finset.mem_union.mp hx' with hxB | hx_ei · exact hBT hxB · have := h_sub i hx_ei exact (Finset.mem_sdiff.mp this).1 · rintro h have : (M i).card = T.card := by rw [h] omega · intro i i' hne hsub have heq : M i = M i' := Finset.eq_of_subset_of_card_le hsub (by rw [hM_card, hM_card]) have h_cancel : ((B ∪ (e i).val) \ B) = ((B ∪ (e i').val) \ B) := by change (M i \ B) = (M i' \ B) rw [heq] rw [Finset.union_sdiff_cancel_left (h_disj i), Finset.union_sdiff_cancel_left (h_disj i')] at h_cancel have he_eq : e i = e i' := Subtype.ext h_cancel have hi_eq : i = i' := e.injective he_eq exact hne hi_eq