AFTD Auto-Formalizing Theoretical Domains

claws_from_packing_compatible

theoremverified

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.

  1. 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.

    lines 3–5

    uses Set.PairwiseDisjoint.subset

      dsimp [is_compatible_repair_family]
      have hO_disj : (↑O : Set (Finset α)).PairwiseDisjoint id := hO.2
      apply Set.PairwiseDisjoint.subset hO_disj
  2. 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.

    lines 6–7

    uses Finset.coe_subset, Finset.biUnion_subset

      rw [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

/-- 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
See it in the graphDiscuss this resultChallenge it