apply_repairs_empty
For any type α with decidable equality and family A : Finset (Finset α), applying the empty repair family to A yields A.
Statement
theorem apply_repairs_empty {α : Type*} [DecidableEq α] (A : Finset (Finset α)) : apply_repairs A ∅ = A
- Source
- folklore
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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
For any type α with decidable equality and any finite set A of finite subsets of α, applying the empty set of repairs to A yields A; that is, apply_repairs A ∅ = A.
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
Applying an empty family of repairs leaves the original set family A unchanged. By definition, applying repairs removes the sets in A that conflict with the union of the repairs and then adjoins the repair sets. Since the repair family is empty, its union is empty, no conflicts exist, and nothing is removed or added.
apply_repairs A ∅ = A
Unfolding the definitions of apply_repairs and conflict_neighborhood expresses apply_repairs A ∅ as (A \ conflict_neighborhood A (∅.biUnion id)) ∪ (∅.biUnion id). Since the union over the empty set is empty, the conflict condition ∃ x ∈ ∅, ¬ Disjoint a x is vacuously false, so the conflict neighborhood is empty. The entire expression reduces to (A \ ∅) ∪ ∅, which simplifies to A.
uses
apply_repairs,conflict_neighborhoodsimp [apply_repairs, conflict_neighborhood]
apply_repairs- The family obtained from A by removing sets conflicting with the union of repair sets in R and then adjoining those repair sets: (A \ conflict_neighborhood A (R.biUnion id)) ∪ (R.biUnion id).
conflict_neighborhood- The subcollection of sets in A that intersect (are not disjoint from) at least one set in X: A.filter (fun a => ∃ x ∈ X, ¬ Disjoint a x).
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 the empty repair family leaves the packing unchanged. -/theorem apply_repairs_empty {α : Type*} [DecidableEq α] (A : Finset (Finset α)) : apply_repairs A ∅ = A := by simp [apply_repairs, conflict_neighborhood]