apply_repairs_is_packing
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.
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.
uses
Finset.mem_biUnionobtain ⟨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
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.
uses
Finset.mem_coe,Finset.mem_sdiffhave 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)
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.
uses
Finset.mem_union,Finset.mem_sdiffrefine ⟨?_, ?_⟩ · 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
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.
uses
Finset.coe_union· rw [apply_repairs, Finset.coe_union] refine hA'disj.union hBdisj ?_
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.
uses
Finset.mem_coe,Finset.mem_sdiff,Finset.mem_filterintro 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
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.
/-- 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⟩