claws_from_packing_compatible
In a weighted k-set packing instance inst over α with decidable equality, any collection of repairs R : Finset (Finset (Finset α)) whose elements are sub-collections of a valid packing O is a compatible repair family.
Statement
theorem claws_from_packing_compatible {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (O : Finset (Finset α)) (hO : is_packing inst O) (R : Finset (Finset (Finset α))) (hR : ∀ X ∈ R, X ⊆ O) : is_compatible_repair_family R
- Source
- arXiv:2610.10036 Sec. 4.2
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
Read back from the Lean
For any type α with decidable equality and any natural number k, given:
- a weighted set packing instance inst : WeightedSetPackingInstance α k,
- a finite set of finite sets O : Finset (Finset α) that is a packing in inst (is_packing inst O), and
- a finite set of finite sets of finite sets R : Finset (Finset (Finset α)) such that every member X ∈ R is a subset of O (X ⊆ O),
R is a compatible repair family (is_compatible_repair_family R).
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
To show that R is a compatible repair family, it suffices to prove that the union of all repair sets in R is pairwise disjoint. Since O is a valid packing, its sets are already pairwise disjoint, a property inherited by any subset of O. Because every repair set in R is assumed to be a subset of O, their union is contained in O, which immediately yields the required disjointness.
It suffices to show that the union of all repairs in R is contained in O.
By definition, R is a compatible repair family (is_compatible_repair_family) if the union ⋃_{X ∈ R} X is pairwise disjoint. Since O is a valid packing (hO), its elements are pairwise disjoint (hO.2). Because any subset of a pairwise disjoint family of sets is also pairwise disjoint (Set.PairwiseDisjoint.subset), the goal reduces to showing that ⋃_{X ∈ R} X ⊆ O.
uses
Set.PairwiseDisjoint.subsetdsimp [is_compatible_repair_family] have hO_disj : (↑O : Set (Finset α)).PairwiseDisjoint id := hO.2 apply Set.PairwiseDisjoint.subset hO_disj
The union of all repairs in R is contained in O.
A union over a family R is contained in O if and only if each element X ∈ R is a subset of O (Finset.coe_subset, Finset.biUnion_subset). This matches the hypothesis hR exactly.
uses
Finset.coe_subset,Finset.biUnion_subsetrw [Finset.coe_subset, Finset.biUnion_subset] exact hR
Set.PairwiseDisjoint.subset- A subset of a pairwise disjoint collection of sets is itself pairwise disjoint.
Finset.coe_subset- Inclusion between finite sets viewed as sets is equivalent to inclusion between the finite sets themselves.
Finset.biUnion_subset- A finite union of sets is a subset of a target set if and only if every constituent set is a subset of the target set.
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.
/-- Claws partitioned from any valid packing form a compatible repair family. -/theorem claws_from_packing_compatible {α : Type*} [DecidableEq α] {k : ℕ} (inst : WeightedSetPackingInstance α k) (O : Finset (Finset α)) (hO : is_packing inst O) (R : Finset (Finset (Finset α))) (hR : ∀ X ∈ R, X ⊆ O) : is_compatible_repair_family R := by dsimp [is_compatible_repair_family] have hO_disj : (↑O : Set (Finset α)).PairwiseDisjoint id := hO.2 apply Set.PairwiseDisjoint.subset hO_disj rw [Finset.coe_subset, Finset.biUnion_subset] exact hR