AFTD Auto-Formalizing Theoretical Domains

finite_three_set_stable_maximum_packings_cover_support

theoremverified

For a finite family of three-element sets, suppose every packing has at most k members and, for each point occurring in the family, some k-member packing omits that point. Then every point occurring in the family is covered by some k-member packing.

Statement

theorem finite_three_set_stable_maximum_packings_cover_support
    {α : Type*} [DecidableEq α] (F : Finset (Finset α)) (k : ℕ)
    (hthree : ∀ t ∈ F, t.card = 3)
    (hmax : ∀ P : Finset (Finset α), P ⊆ F →
      (P : Set (Finset α)).Pairwise Disjoint → P.card ≤ k)
    (hstable : ∀ y ∈ F.biUnion id, ∃ P : Finset (Finset α),
      P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧
      ∀ s ∈ P, y ∉ s) :
    ∀ x ∈ F.biUnion id, ∃ P : Finset (Finset α),
      P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧
      ∃ s ∈ P, x ∈ s
Source
Elementary packing exchange for the triangle packing-cover campaign, related to arXiv:2610.15539, Section 1.
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 3

The proof, explained

The proof proceeds by contradiction: suppose an element x in the support of F is not covered by any maximum packing (a packing of size k). Choosing a 3-element set T = {x, y, z} in F containing x, the stability assumption gives a maximum packing P avoiding y, which by hypothesis must also avoid x. If no block of P contained z, adjoining T to P would create a packing of size k + 1, contradicting the maximum packing size k. Therefore, exactly one block r in P contains z; replacing r with T produces a valid packing of size k that covers x, providing the desired contradiction.

  1. There is a 3-element set T = {x, y, z} in F containing x with y ≠ z.

    Let x be an element in the support of F (that is, x ∈ ⋃ F). By definition of the union, x ∈ T for some T ∈ F. Since every set in F has cardinality 3, removing x leaves a 2-element set T \ {x} = {y, z} with y ≠ z. Reinserting x gives T = {x, y, z}, so y ∈ T and z ∈ T as well.

    lines 12–24

    uses Finset.mem_biUnion.mp, Finset.card_erase_of_mem, Finset.card_eq_two.mp, Finset.insert_erase

      classical
      intro x hx
      obtain ⟨T, hTF, hxT⟩ := Finset.mem_biUnion.mp hx
      change x ∈ T at hxT
      have herase : (T.erase x).card = 2 := by
        rw [Finset.card_erase_of_mem hxT, hthree T hTF]
      obtain ⟨y, z, hyz, hyzT⟩ := Finset.card_eq_two.mp herase
      have hTx : T = {x, y, z} := by
        have hh := Finset.insert_erase hxT
        rw [hyzT] at hh
        simpa using hh.symm
      have hyT : y ∈ T := by rw [hTx]; simp
      have hzT : z ∈ T := by rw [hTx]; simp
  2. Assuming no k-member packing covers x, there is a k-member packing P ⊆ F avoiding both x and y.

    We proceed by contradiction: assume no pairwise disjoint family of k sets in F covers x. Since y ∈ T ∈ F, y is in the support of F. By the stability hypothesis (`hstable`), there is a packing P ⊆ F of size k avoiding y. By the contradiction assumption, P cannot cover x either, so every set s ∈ P avoids both x and y.

    lines 25–30

    uses Finset.mem_biUnion.mpr

      by_contra hfail
      have hyF : y ∈ F.biUnion id := Finset.mem_biUnion.mpr ⟨T, hTF, hyT⟩
      obtain ⟨P, hPF, hPd, hPk, hPy⟩ := hstable y hyF
      have hPx : ∀ s ∈ P, x ∉ s := by
        intro s hs hxs
        exact hfail ⟨P, hPF, hPd, hPk, s, hs, hxs⟩
  3. Any set s ∈ P not containing z is disjoint from T.

    Since T = {x, y, z}, any element in T ∩ s must be x, y, or z. But no s ∈ P contains x (by the contradiction hypothesis) or y (by the choice of P). Thus, if z ∉ s, s contains none of the elements of T, so T and s are disjoint.

    lines 31–40

    uses Finset.disjoint_left.mpr, Finset.mem_insert, Finset.mem_singleton

      have hdisT : ∀ s ∈ P, z ∉ s → Disjoint T s := by
        intro s hs hzs
        apply Finset.disjoint_left.mpr
        intro a ha has
        rw [hTx] at ha
        simp only [Finset.mem_insert, Finset.mem_singleton] at ha
        rcases ha with rfl | rfl | rfl
        · exact hPx s hs has
        · exact hPy s hs has
        · exact hzs has
  4. Some member r ∈ P contains z.

    Suppose, for contradiction, that no member of P contains z. Then by the previous step, T is disjoint from every member of P. Moreover, T ∉ P because x ∈ T while all members of P avoid x. Thus P ∪ {T} would be a pairwise disjoint subfamily of F of size |P| + 1 = k + 1. But the maximality hypothesis (`hmax`) asserts that any packing in F has size at most k, which would force k + 1 ≤ k. This contradiction shows that some r ∈ P must contain z.

    lines 41–63

    uses Finset.mem_insert.mp, Finset.mem_coe, Finset.mem_insert, Finset.card_insert_of_notMem

      have hrex : ∃ r ∈ P, z ∈ r := by
        by_contra hno
        have hnoz : ∀ s ∈ P, z ∉ s := by simpa using hno
        have hnot : T ∉ P := by
          intro hTP
          exact hPx T hTP hxT
        have hsub : insert T P ⊆ F := by
          intro s hs
          rcases Finset.mem_insert.mp hs with rfl | hs
          · exact hTF
          · exact hPF hs
        have hpair : ((insert T P : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by
          intro s hs t ht hne
          simp only [Finset.mem_coe, Finset.mem_insert] at hs ht
          rcases hs with rfl | hs <;> rcases ht with rfl | ht
          · exact (hne rfl).elim
          · exact hdisT t ht (hnoz t ht)
          · exact (hdisT s hs (hnoz s hs)).symm
          · exact hPd hs ht hne
        have hc := hmax (insert T P) hsub hpair
        rw [Finset.card_insert_of_notMem hnot, hPk] at hc
        omega
      obtain ⟨r, hrP, hzr⟩ := hrex
  5. T ∉ P, and T is disjoint from every set in P \ {r}.

    First, T ∉ P because x ∈ T and no set in P contains x. Second, the sets in P are pairwise disjoint. Since z ∈ r, no other set s ∈ P \ {r} can contain z. By the disjointness property established earlier, every such s is disjoint from T.

    lines 64–74

    uses Finset.mem_erase.mp, Finset.disjoint_left.mp

      have hnot : T ∉ P := by
        intro hTP
        exact hPx T hTP hxT
      have hrest : ∀ s ∈ P.erase r, Disjoint T s := by
        intro s hs
        have hsP := (Finset.mem_erase.mp hs).2
        have hsr := (Finset.mem_erase.mp hs).1
        apply hdisT s hsP
        intro hzs
        have hd := hPd hsP hrP hsr
        exact (Finset.disjoint_left.mp hd) hzs hzr
  6. Replacing r with T in P gives a k-member packing covering x, reaching a contradiction.

    Define Q = (P \ {r}) ∪ {T}. Since T ∈ F and P ⊆ F, we have Q ⊆ F. The family Q is pairwise disjoint because P \ {r} is pairwise disjoint and T is disjoint from every member of P \ {r}. Since r ∈ P and T ∉ P, we have |Q| = |P| - 1 + 1 = k (with k > 0 because r ∈ P). Thus Q is a k-member packing covering x (via T ∈ Q and x ∈ T), contradicting the assumption that no such packing exists.

    lines 75–96

    uses Finset.mem_insert, Finset.mem_erase, Finset.mem_coe, Finset.mem_erase.mpr, Finset.card_insert_of_notMem, Finset.mem_of_mem_erase, Finset.card_erase_of_mem, Finset.card_pos.mpr, Finset.mem_insert_self

      let Q : Finset (Finset α) := insert T (P.erase r)
      have hQF : Q ⊆ F := by
        intro s hs
        simp only [Q, Finset.mem_insert, Finset.mem_erase] at hs
        rcases hs with rfl | ⟨_, hs⟩
        · exact hTF
        · exact hPF hs
      have hQd : (Q : Set (Finset α)).Pairwise Disjoint := by
        intro s hs t ht hne
        simp only [Q, Finset.mem_coe, Finset.mem_insert, Finset.mem_erase] at hs ht
        rcases hs with rfl | ⟨hsr, hs⟩ <;> rcases ht with rfl | ⟨htr, ht⟩
        · exact (hne rfl).elim
        · exact hrest t (Finset.mem_erase.mpr ⟨htr, ht⟩)
        · exact (hrest s (Finset.mem_erase.mpr ⟨hsr, hs⟩)).symm
        · exact hPd hs ht hne
      have hQk : Q.card = k := by
        change (insert T (P.erase r)).card = k
        rw [Finset.card_insert_of_notMem (fun h => hnot (Finset.mem_of_mem_erase h)),
          Finset.card_erase_of_mem hrP, hPk]
        have : 0 < k := by rw [← hPk]; exact Finset.card_pos.mpr ⟨r, hrP⟩
        omega
      exact hfail ⟨Q, hQF, hQd, hQk, T, Finset.mem_insert_self _ _, hxT⟩
Finset.mem_biUnion.mp
An element belongs to an indexed union of finsets if and only if it belongs to one of the component finsets.
Finset.mem_biUnion.mpr
If an element belongs to a component finset of an indexed union, it belongs to the union.
Finset.card_erase_of_mem
Removing an element from a finset containing it decreases its cardinality by 1.
Finset.card_eq_two.mp
A finset has cardinality 2 if and only if it consists of two distinct elements.
Finset.insert_erase
Reinserting an element into a finset from which it was removed restores the original finset.
Finset.disjoint_left.mpr
Two finsets are disjoint if no element of the first belongs to the second.
Finset.disjoint_left.mp
If two finsets are disjoint, no element of the first belongs to the second.
Finset.mem_insert
An element belongs to `insert b s` if and only if it equals b or belongs to s.
Finset.mem_insert.mp
If an element belongs to `insert b s`, it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton `{a}` if and only if it equals a.
Finset.mem_coe
Membership in a finset is equivalent to membership in its coercion to a set.
Finset.card_insert_of_notMem
Inserting an element not already in a finset increases its cardinality by 1.
Finset.mem_erase.mp
If an element belongs to `s.erase a`, it belongs to s and is distinct from a.
Finset.mem_erase
An element belongs to `s.erase a` if and only if it is distinct from a and belongs to s.
Finset.mem_erase.mpr
If an element is distinct from a and belongs to s, it belongs to `s.erase a`.
Finset.mem_of_mem_erase
Any element of `s.erase a` belongs to s.
Finset.card_pos.mpr
A nonempty finset has strictly positive cardinality.
Finset.mem_insert_self
An element always belongs to the finset obtained by inserting it into any finset.

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

theorem finite_three_set_stable_maximum_packings_cover_support    {α : Type*} [DecidableEq α] (F : Finset (Finset α)) (k : ℕ)    (hthree : ∀ t ∈ F, t.card = 3)    (hmax : ∀ P : Finset (Finset α), P ⊆ F →      (P : Set (Finset α)).Pairwise Disjoint → P.card ≤ k)    (hstable : ∀ y ∈ F.biUnion id, ∃ P : Finset (Finset α),      P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧      ∀ s ∈ P, y ∉ s) :    ∀ x ∈ F.biUnion id, ∃ P : Finset (Finset α),      P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧      ∃ s ∈ P, x ∈ s := by  classical  intro x hx  obtain ⟨T, hTF, hxT⟩ := Finset.mem_biUnion.mp hx  change x ∈ T at hxT  have herase : (T.erase x).card = 2 := by    rw [Finset.card_erase_of_mem hxT, hthree T hTF]  obtain ⟨y, z, hyz, hyzT⟩ := Finset.card_eq_two.mp herase  have hTx : T = {x, y, z} := by    have hh := Finset.insert_erase hxT    rw [hyzT] at hh    simpa using hh.symm  have hyT : y ∈ T := by rw [hTx]; simp  have hzT : z ∈ T := by rw [hTx]; simp  by_contra hfail  have hyF : y ∈ F.biUnion id := Finset.mem_biUnion.mpr ⟨T, hTF, hyT⟩  obtain ⟨P, hPF, hPd, hPk, hPy⟩ := hstable y hyF  have hPx : ∀ s ∈ P, x ∉ s := by    intro s hs hxs    exact hfail ⟨P, hPF, hPd, hPk, s, hs, hxs⟩  have hdisT : ∀ s ∈ P, z ∉ s → Disjoint T s := by    intro s hs hzs    apply Finset.disjoint_left.mpr    intro a ha has    rw [hTx] at ha    simp only [Finset.mem_insert, Finset.mem_singleton] at ha    rcases ha with rfl | rfl | rfl    · exact hPx s hs has    · exact hPy s hs has    · exact hzs has  have hrex : ∃ r ∈ P, z ∈ r := by    by_contra hno    have hnoz : ∀ s ∈ P, z ∉ s := by simpa using hno    have hnot : T ∉ P := by      intro hTP      exact hPx T hTP hxT    have hsub : insert T P ⊆ F := by      intro s hs      rcases Finset.mem_insert.mp hs with rfl | hs      · exact hTF      · exact hPF hs    have hpair : ((insert T P : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by      intro s hs t ht hne      simp only [Finset.mem_coe, Finset.mem_insert] at hs ht      rcases hs with rfl | hs <;> rcases ht with rfl | ht      · exact (hne rfl).elim      · exact hdisT t ht (hnoz t ht)      · exact (hdisT s hs (hnoz s hs)).symm      · exact hPd hs ht hne    have hc := hmax (insert T P) hsub hpair    rw [Finset.card_insert_of_notMem hnot, hPk] at hc    omega  obtain ⟨r, hrP, hzr⟩ := hrex  have hnot : T ∉ P := by    intro hTP    exact hPx T hTP hxT  have hrest : ∀ s ∈ P.erase r, Disjoint T s := by    intro s hs    have hsP := (Finset.mem_erase.mp hs).2    have hsr := (Finset.mem_erase.mp hs).1    apply hdisT s hsP    intro hzs    have hd := hPd hsP hrP hsr    exact (Finset.disjoint_left.mp hd) hzs hzr  let Q : Finset (Finset α) := insert T (P.erase r)  have hQF : Q ⊆ F := by    intro s hs    simp only [Q, Finset.mem_insert, Finset.mem_erase] at hs    rcases hs with rfl | ⟨_, hs⟩    · exact hTF    · exact hPF hs  have hQd : (Q : Set (Finset α)).Pairwise Disjoint := by    intro s hs t ht hne    simp only [Q, Finset.mem_coe, Finset.mem_insert, Finset.mem_erase] at hs ht    rcases hs with rfl | ⟨hsr, hs⟩ <;> rcases ht with rfl | ⟨htr, ht⟩    · exact (hne rfl).elim    · exact hrest t (Finset.mem_erase.mpr ⟨htr, ht⟩)    · exact (hrest s (Finset.mem_erase.mpr ⟨hsr, hs⟩)).symm    · exact hPd hs ht hne  have hQk : Q.card = k := by    change (insert T (P.erase r)).card = k    rw [Finset.card_insert_of_notMem (fun h => hnot (Finset.mem_of_mem_erase h)),      Finset.card_erase_of_mem hrP, hPk]    have : 0 < k := by rw [← hPk]; exact Finset.card_pos.mpr ⟨r, hrP⟩    omega  exact hfail ⟨Q, hQF, hQd, hQk, T, Finset.mem_insert_self _ _, hxT⟩
See it in the graphDiscuss this resultChallenge it