AFTD Auto-Formalizing Theoretical Domains

apply_repairs_is_packing

theoremverified

In a weighted k-set packing instance inst over α with decidable equality, applying a compatible family of repairs R whose sets belong to inst.family to a valid packing A yields a valid packing.

Statement

theorem apply_repairs_is_packing {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A : Finset (Finset α)) (R : Finset (Finset (Finset α))) (hA : is_packing inst A) (hR_sub : ∀ X ∈ R, X ⊆ inst.family) (hR_comp : is_compatible_repair_family R) : is_packing inst (apply_repairs A R)
Source
arXiv:2610.10036 Sec. 4.2
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • WeightedSetPackingInstanceFor a type α with decidable equality and k : ℕ, an instance of Maximum Weighted k-Set Packing WeightedSetPackingInstance α k consists of a…
  • is_packingGiven an instance inst of weighted k-set packing on a type α with decidable equality, a sub-collection A : Finset (Finset α) is a packing…
  • is_compatible_repair_familyFor a type α with decidable equality, a finite collection of repairs R : Finset (Finset (Finset α)) is compatible…
  • apply_repairsGiven a type α with decidable equality, a family A : Finset (Finset α), and a collection of repairs R : Finset (Finset (Finset α)),…
  • conflict_neighborhoodGiven a type α with decidable equality and two finite collections of finite subsets of α, A and X (both of type Finset (Finset α)),…

Read back from the Lean

Let α be a type with decidable equality and let k be a natural number. Let inst be a WeightedSetPackingInstance α k, let A be a finite set of finite subsets of α, and let R be a finite set of finite collections of finite subsets of α. Assume that: 1. A is a packing for inst (meaning A ⊆ inst.family and the elements of A are pairwise disjoint), 2. every collection X ∈ R satisfies X ⊆ inst.family, and 3. R is a compatible repair family (meaning the elements of ⋃ X ∈ R, X are pairwise disjoint). Then the repaired family apply_repairs A R—formed by removing from A every set that intersects some set in ⋃ X ∈ R, X, and then taking the union with ⋃ X ∈ R, X—is also a packing for inst (it is a subset of inst.family and its elements are pairwise disjoint).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof decomposes the repaired collection apply_repairs(A, R) into the retained sets A \ conflict_neighborhood(A, ⋃ R) and the repair sets ⋃ R. Every set in both pieces belongs to inst.family because A ⊆ inst.family and each repair X ∈ R satisfies X ⊆ inst.family. Finally, the repaired collection is pairwise disjoint because the retained sets inherit disjointness from A, the repairs are pairwise disjoint by compatibility of R, and any potential cross-conflicts were explicitly discarded by removing the conflict neighborhood of ⋃ R from A.

  1. The packing A and the union of repair sets ⋃ R both consist of sets belonging to inst.family, and A is pairwise disjoint.

    We unpack the assumption that A is a valid packing into two facts: every set in A belongs to inst.family, and A is pairwise disjoint. We then show that every set s in the repair union ⋃ R also belongs to inst.family: by definition of the union, s belongs to some repair X ∈ R, and by hypothesis every repair satisfies X ⊆ inst.family.

    lines 3–8

    uses Finset.mem_biUnion

      obtain ⟨hAfam, hAdisj⟩ := hA
      have hBfam : R.biUnion id ⊆ inst.family := by
        intro s hs
        rw [Finset.mem_biUnion] at hs
        obtain ⟨X, hX, hsX⟩ := hs
        exact hR_sub X hX hsX
  2. Both the repair union ⋃ R and the retained sets A \ conflict_neighborhood(A, ⋃ R) are internally pairwise disjoint.

    The union of repairs ⋃ R is pairwise disjoint directly by the hypothesis that R is a compatible repair family. The retained sets A \ conflict_neighborhood(A, ⋃ R) form a subset of A, so they inherit pairwise disjointness from A.

    lines 9–11

    uses Finset.mem_coe, Finset.mem_sdiff

      have hBdisj : (↑(R.biUnion id) : Set (Finset α)).PairwiseDisjoint id := hR_comp
      have hA'disj : (↑(A \ conflict_neighborhood A (R.biUnion id)) : Set (Finset α)).PairwiseDisjoint id :=
        hAdisj.subset (by intro x hx; simp only [Finset.mem_coe, Finset.mem_sdiff] at hx ⊢; exact hx.1)
  3. Every set in apply_repairs(A, R) belongs to inst.family.

    To show that apply_repairs(A, R) is a packing, we split the goal into family membership and pairwise disjointness. For membership, any set s in the repaired collection is either a retained set from A or a repair set from ⋃ R; in either case, it belongs to inst.family.

    lines 12–17

    uses Finset.mem_union, Finset.mem_sdiff

      refine ⟨?_, ?_⟩
      · intro s hs
        simp only [apply_repairs, Finset.mem_union, Finset.mem_sdiff] at hs
        rcases hs with ⟨hsA, _⟩ | hsB
        · exact hAfam hsA
        · exact hBfam hsB
  4. To establish that apply_repairs(A, R) is pairwise disjoint, it suffices to show that every retained set is disjoint from every repair set.

    By definition, apply_repairs(A, R) is the union of the retained sets A \ conflict_neighborhood(A, ⋃ R) and the repair sets ⋃ R. Since both collections are already known to be pairwise disjoint, their union is pairwise disjoint as long as there is no overlap between an element of the first and an element of the second.

    lines 18–19

    uses Finset.coe_union

      · rw [apply_repairs, Finset.coe_union]
        refine hA'disj.union hBdisj ?_
  5. Every retained set is disjoint from every repair set, completing the proof that apply_repairs(A, R) is a valid packing.

    Let i be a retained set and j ∈ ⋃ R. Since i ∉ conflict_neighborhood(A, ⋃ R), i has no conflicts with any set in ⋃ R. Assuming for contradiction that i and j are not disjoint immediately contradicts this property, since j ∈ ⋃ R.

    lines 20–26

    uses Finset.mem_coe, Finset.mem_sdiff, Finset.mem_filter

        intro i hi j hj _
        simp only [Finset.mem_coe, Finset.mem_sdiff] at hi
        have hnot : ¬ ∃ x ∈ R.biUnion id, ¬ Disjoint i x := by
          intro h
          exact hi.2 (by simp only [conflict_neighborhood, Finset.mem_filter]; exact ⟨hi.1, h⟩)
        by_contra hdj
        exact hnot ⟨j, hj, hdj⟩
Finset.mem_biUnion
An element belongs to the indexed union of a family of finsets if and only if it belongs to one of the constituent finsets.
Finset.mem_coe
An element belongs to the set coercion of a finset if and only if it belongs to the finset.
Finset.mem_sdiff
An element belongs to the set difference of two finsets if and only if it belongs to the first finset and does not belong to the second.
Finset.mem_union
An element belongs to the union of two finsets if and only if it belongs to at least one of them.
Finset.coe_union
The set coercion of the union of two finsets is the union of their individual set coercions.
Finset.mem_filter
An element belongs to the sub-finset filtered by a predicate if and only if it belongs to the original finset and satisfies the predicate.

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

/-- Applying a compatible family of repairs from the family yields a valid packing. -/theorem apply_repairs_is_packing {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (A : Finset (Finset α)) (R : Finset (Finset (Finset α))) (hA : is_packing inst A) (hR_sub : ∀ X ∈ R, X ⊆ inst.family) (hR_comp : is_compatible_repair_family R) : is_packing inst (apply_repairs A R) := by  obtain ⟨hAfam, hAdisj⟩ := hA  have hBfam : R.biUnion id ⊆ inst.family := by    intro s hs    rw [Finset.mem_biUnion] at hs    obtain ⟨X, hX, hsX⟩ := hs    exact hR_sub X hX hsX  have hBdisj : (↑(R.biUnion id) : Set (Finset α)).PairwiseDisjoint id := hR_comp  have hA'disj : (↑(A \ conflict_neighborhood A (R.biUnion id)) : Set (Finset α)).PairwiseDisjoint id :=    hAdisj.subset (by intro x hx; simp only [Finset.mem_coe, Finset.mem_sdiff] at hx ⊢; exact hx.1)  refine ⟨?_, ?_⟩  · intro s hs    simp only [apply_repairs, Finset.mem_union, Finset.mem_sdiff] at hs    rcases hs with ⟨hsA, _⟩ | hsB    · exact hAfam hsA    · exact hBfam hsB  · rw [apply_repairs, Finset.coe_union]    refine hA'disj.union hBdisj ?_    intro i hi j hj _    simp only [Finset.mem_coe, Finset.mem_sdiff] at hi    have hnot : ¬ ∃ x ∈ R.biUnion id, ¬ Disjoint i x := by      intro h      exact hi.2 (by simp only [conflict_neighborhood, Finset.mem_filter]; exact ⟨hi.1, h⟩)    by_contra hdj    exact hnot ⟨j, hj, hdj⟩
See it in the graphDiscuss this resultChallenge it