AFTD Auto-Formalizing Theoretical Domains

finite_maximum_packing_extend_of_small_conflict_neighborhood

theoremverified

A packing W in a finite set family extends to a maximum packing if it intersects no more members of a fixed maximum packing P than W has members.

Statement

theorem finite_maximum_packing_extend_of_small_conflict_neighborhood
    {α : Type*} [DecidableEq α] (F P W : Finset (Finset α))
    (hnonempty : ∀ t ∈ F, t.Nonempty)
    (hPF : P ⊆ F) (hWF : W ⊆ F)
    (hPdis : (P : Set (Finset α)).Pairwise Disjoint)
    (hWdis : (W : Set (Finset α)).Pairwise Disjoint)
    (hmax : ∀ Q : Finset (Finset α), Q ⊆ F →
      (Q : Set (Finset α)).Pairwise Disjoint → Q.card ≤ P.card)
    (hconf : (P.filter fun s => ¬ Disjoint s (W.biUnion id)).card ≤ W.card) :
    ∃ Q : Finset (Finset α), Q ⊆ F ∧
      (Q : Set (Finset α)).Pairwise Disjoint ∧ Q.card = P.card ∧ W ⊆ Q
Source
Elementary packing exchange in the triangle packing-cover campaign, related to arXiv:2610.15539, Section 1.
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The proof constructs an extension Q by removing from the maximum packing P the conflict neighborhood N (the elements of P that intersect some member of W) and replacing them with W, setting Q = (P \ N) ∪ W. Because the remaining elements of P avoid the union of W, the family Q remains pairwise disjoint and contains W by construction. The condition |N| ≤ |W| guarantees that |Q| = |P| - |N| + |W| ≥ |P|, which by the maximality of P forces |Q| = |P|, proving that Q is a maximum packing extending W.

  1. Define the conflict neighborhood N ⊆ P and candidate extension Q.

    We identify N as the subcollection of sets in P that intersect the union of W, and define Q = (P \ N) ∪ W as the candidate packing extending W.

    lines 12–14

      open Finset in
      set N := P.filter fun s => ¬ Disjoint s (W.biUnion id)
      set Q := (P \ N) ∪ W
  2. Q is a subcollection of F (Q ⊆ F).

    Because P ⊆ F, the difference P \ N is also a subset of F. Since both P \ N ⊆ F and W ⊆ F, their union Q = (P \ N) ∪ W is contained in F.

    line 15

    uses Finset.union_subset

      have hQF : Q ⊆ F := Finset.union_subset (Finset.sdiff_subset.trans hPF) hWF
  3. The elements of Q are pairwise disjoint.

    Let a and b be distinct elements of Q = (P \ N) ∪ W. If both belong to P \ N, they are disjoint because P is pairwise disjoint. If a ∈ P \ N and b ∈ W, then by definition of N, a is disjoint from the union of all sets in W, hence disjoint from b; the case where a ∈ W and b ∈ P \ N is symmetric. Finally, if both belong to W, they are disjoint because W is pairwise disjoint.

    lines 16–35

    uses Finset.disjoint_biUnion_right

      have hQdis : (Q : Set (Finset α)).Pairwise Disjoint := by
        intro a ha b hb hab
        rw [Finset.mem_coe] at ha hb
        change a ∈ (P \ N) ∪ W at ha
        change b ∈ (P \ N) ∪ W at hb
        rw [Finset.mem_union] at ha hb
        rcases ha with ha | haW
        · rw [Finset.mem_sdiff, Finset.mem_filter, not_and, not_not] at ha
          rcases hb with hb | hbW
          · rw [Finset.mem_sdiff] at hb
            exact hPdis ha.1 hb.1 hab
          · have hd := ha.2 ha.1
            rw [Finset.disjoint_biUnion_right] at hd
            exact hd b hbW
        · rcases hb with hb | hbW
          · rw [Finset.mem_sdiff, Finset.mem_filter, not_and, not_not] at hb
            have hd := hb.2 hb.1
            rw [Finset.disjoint_biUnion_right] at hd
            exact (hd a haW).symm
          · exact hWdis haW hbW hab
  4. The families P \ N and W are disjoint.

    Suppose, for contradiction, that some set x belongs to both P \ N and W. Since x ∈ P \ N, it is disjoint from every set in W, which implies x is disjoint from itself. Therefore x must be empty, contradicting the hypothesis that every set in F is nonempty.

    lines 36–45

    uses Finset.disjoint_left, Finset.disjoint_biUnion_right, disjoint_self.mp

      have hdisj : Disjoint (P \ N) W := by
        rw [Finset.disjoint_left]
        intro x hx hxW
        rw [Finset.mem_sdiff, Finset.mem_filter, not_and, not_not] at hx
        have hd := hx.2 hx.1
        rw [Finset.disjoint_biUnion_right] at hd
        have hxx : Disjoint x x := hd x hxW
        have he : x = ∅ := disjoint_self.mp hxx
        have hne : x.Nonempty := hnonempty x (hWF hxW)
        exact hne.ne_empty he
  5. Q has the same cardinality as P (|Q| = |P|).

    Because Q ⊆ F is pairwise disjoint and P is a maximum packing, |Q| ≤ |P|. Conversely, because P \ N and W are disjoint families of sets, |Q| = |P \ N| + |W| = (|P| - |N|) + |W|. Since |N| ≤ |W| by hypothesis, linear arithmetic shows |Q| ≥ |P|. By antisymmetry of ≤, |Q| = |P|.

    lines 46–54

    uses Finset.card_union_of_disjoint, Finset.card_sdiff_of_subset, Finset.filter_subset, Finset.card_le_card, le_antisymm

      have hQcard : Q.card = P.card := by
        have h1 : Q.card ≤ P.card := hmax Q hQF hQdis
        have h2 : Q.card = (P \ N).card + W.card := Finset.card_union_of_disjoint hdisj
        have h3 : (P \ N).card = P.card - N.card := Finset.card_sdiff_of_subset (Finset.filter_subset _ P)
        have h4 : N.card ≤ P.card := Finset.card_le_card (Finset.filter_subset _ P)
        have h5 : P.card ≤ Q.card := by
          rw [h2, h3]
          omega
        exact le_antisymm h1 h5
  6. There exists a maximum packing extending W, witnessed by Q.

    We return Q as the desired packing: it is a subcollection of F, consists of pairwise disjoint sets, has size |Q| = |P|, and contains W by definition of Q as a union with W.

    line 55

    uses Finset.subset_union_right

      exact ⟨Q, hQF, hQdis, hQcard, Finset.subset_union_right⟩
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is less than or equal to the other's.
Finset.card_sdiff_of_subset
If s is a subset of t, the cardinality of the difference t \ s is |t| - |s|.
Finset.disjoint_biUnion_right
A set is disjoint from a union of sets if and only if it is disjoint from each member of the union.
Finset.disjoint_left
Two sets are disjoint if and only if no element of the first belongs to the second.
Finset.filter_subset
Filtering a finite set by a predicate produces a subset of the original set.
Finset.subset_union_right
Every set is a subset of any union containing it.
Finset.union_subset
A union of two sets is a subset of a third set if and only if both sets are subsets of it.
disjoint_self.mp
A set disjoint from itself is empty.
le_antisymm
If a ≤ b and b ≤ a, then a = b.

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_maximum_packing_extend_of_small_conflict_neighborhood    {α : Type*} [DecidableEq α] (F P W : Finset (Finset α))    (hnonempty : ∀ t ∈ F, t.Nonempty)    (hPF : P ⊆ F) (hWF : W ⊆ F)    (hPdis : (P : Set (Finset α)).Pairwise Disjoint)    (hWdis : (W : Set (Finset α)).Pairwise Disjoint)    (hmax : ∀ Q : Finset (Finset α), Q ⊆ F →      (Q : Set (Finset α)).Pairwise Disjoint → Q.card ≤ P.card)    (hconf : (P.filter fun s => ¬ Disjoint s (W.biUnion id)).card ≤ W.card) :    ∃ Q : Finset (Finset α), Q ⊆ F ∧      (Q : Set (Finset α)).Pairwise Disjoint ∧ Q.card = P.card ∧ W ⊆ Q := by  open Finset in  set N := P.filter fun s => ¬ Disjoint s (W.biUnion id)  set Q := (P \ N) ∪ W  have hQF : Q ⊆ F := Finset.union_subset (Finset.sdiff_subset.trans hPF) hWF  have hQdis : (Q : Set (Finset α)).Pairwise Disjoint := by    intro a ha b hb hab    rw [Finset.mem_coe] at ha hb    change a ∈ (P \ N) ∪ W at ha    change b ∈ (P \ N) ∪ W at hb    rw [Finset.mem_union] at ha hb    rcases ha with ha | haW    · rw [Finset.mem_sdiff, Finset.mem_filter, not_and, not_not] at ha      rcases hb with hb | hbW      · rw [Finset.mem_sdiff] at hb        exact hPdis ha.1 hb.1 hab      · have hd := ha.2 ha.1        rw [Finset.disjoint_biUnion_right] at hd        exact hd b hbW    · rcases hb with hb | hbW      · rw [Finset.mem_sdiff, Finset.mem_filter, not_and, not_not] at hb        have hd := hb.2 hb.1        rw [Finset.disjoint_biUnion_right] at hd        exact (hd a haW).symm      · exact hWdis haW hbW hab  have hdisj : Disjoint (P \ N) W := by    rw [Finset.disjoint_left]    intro x hx hxW    rw [Finset.mem_sdiff, Finset.mem_filter, not_and, not_not] at hx    have hd := hx.2 hx.1    rw [Finset.disjoint_biUnion_right] at hd    have hxx : Disjoint x x := hd x hxW    have he : x = ∅ := disjoint_self.mp hxx    have hne : x.Nonempty := hnonempty x (hWF hxW)    exact hne.ne_empty he  have hQcard : Q.card = P.card := by    have h1 : Q.card ≤ P.card := hmax Q hQF hQdis    have h2 : Q.card = (P \ N).card + W.card := Finset.card_union_of_disjoint hdisj    have h3 : (P \ N).card = P.card - N.card := Finset.card_sdiff_of_subset (Finset.filter_subset _ P)    have h4 : N.card ≤ P.card := Finset.card_le_card (Finset.filter_subset _ P)    have h5 : P.card ≤ Q.card := by      rw [h2, h3]      omega    exact le_antisymm h1 h5  exact ⟨Q, hQF, hQdis, hQcard, Finset.subset_union_right⟩
See it in the graphDiscuss this resultChallenge it