AFTD Auto-Formalizing Theoretical Domains

five_diamond_copy_of_monochromatic_level

theoremverified

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.

  1. |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.

    lines 13–15

    uses Finset.card_sdiff_of_subset

      have hTB_card : (T \ B).card = 4 := by
        have := Finset.card_sdiff_of_subset hBT
        omega
  2. 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.

    lines 16–18

    uses Finset.card_powersetCard

      have hP_card : ((T \ B).powersetCard 2).card = 6 := by
        rw [Finset.card_powersetCard, hTB_card]
        rfl
  3. 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.

    lines 19–21

    uses Finset.exists_subset_card_eq

      obtain ⟨s, hs_sub, hs_card⟩ : ∃ s ⊆ (T \ B).powersetCard 2, s.card = 5 := by
        apply Finset.exists_subset_card_eq
        omega
  4. 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.

    lines 22–31

    uses Finset.equivFinOfCardEq, Finset.card_union_of_disjoint

      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
  5. 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).

    lines 32–34

    uses Finset.ssubset_iff_subset_ne

      have hBT_ssub : B ⊂ T := by
        rw [Finset.ssubset_iff_subset_ne]
        exact ⟨hBT, by rintro rfl; omega⟩
  6. 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.

    line 35

      refine ⟨M, hB, hT, fun i => h_level (M i) (hM_card i), hBT_ssub, ?_, ?_⟩
  7. 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.

    lines 36–54

    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
  8. 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.

    lines 55–63

    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

/-- 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
See it in the graphDiscuss this resultChallenge it