finite_packing_good_of_family_subset
If F is a subfamily of F-prime and a fixed packing has no member entirely covered by edges of F-prime that meet the packing in exactly one edge, then the same holds for F.
Statement
theorem finite_packing_good_of_family_subset {E : Type} [DecidableEq E] (F F' P : Finset (Finset E)) (hFF' : F ⊆ F') (hgood : ∀ p ∈ P, ¬ p ⊆ ((F'.filter (fun t => (t ∩ P.biUnion id).card = 1)).biUnion id)) : ∀ p ∈ P, ¬ p ⊆ ((F.filter (fun t => (t ∩ P.biUnion id).card = 1)).biUnion id)
- Source
- Monotonicity step for simple_graph_packing_thirteen_stable_seed_good_packing.
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem is proved by contradiction. Suppose some member p ∈ P were covered by edges in F that intersect the packing ⋃ P in exactly one element. Since F ⊆ F', every such edge is also in F' and has the exact same singleton intersection with ⋃ P, so p would also be covered by the corresponding edges of F', directly contradicting the goodness hypothesis for F'.
To derive a contradiction, it suffices to show that p is covered by the union of edges in F' that meet ⋃ P in exactly one element.
Suppose, for contradiction, that some p ∈ P is covered by the edges of F that intersect ⋃ P in exactly one element (hypothesis `hsub`). By the assumption on F' (`hgood`), no member of P can be covered by the corresponding edges of F'. Applying `hgood` to p reduces the goal to showing that p is a subset of the union of such edges from F'.
intro p hp hsub apply hgood p hp
Every element of p belongs to the union of edges in F' that meet ⋃ P in exactly one element.
Let e ∈ p. By the covering assumption for F, e belongs to some edge t in the filtered collection for F (using `Finset.mem_biUnion.mp`). Unpacking this with `Finset.mem_filter.mp` gives t ∈ F and |t ∩ ⋃ P| = 1. Since F ⊆ F' (`hFF'`), we have t ∈ F', so t satisfies the filter condition for F' as well (`Finset.mem_filter.mpr`). Consequently, e is contained in the union of edges in F' that meet ⋃ P in a single element (`Finset.mem_biUnion.mpr`), which completes the proof.
uses
Finset.mem_biUnion.mp,Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_biUnion.mprintro e he obtain ⟨t,ht,het⟩ := Finset.mem_biUnion.mp (hsub he) obtain ⟨htF,htcard⟩ := Finset.mem_filter.mp ht exact Finset.mem_biUnion.mpr ⟨t,Finset.mem_filter.mpr ⟨hFF' htF,htcard⟩,het⟩
Finset.mem_biUnion.mp- An element belongs to a union ⋃_{a ∈ s} f(a) only if it belongs to f(a) for some a ∈ s.
Finset.mem_filter.mp- An element in a filtered set {x ∈ s | P(x)} belongs to s and satisfies the predicate P.
Finset.mem_filter.mpr- If an element belongs to s and satisfies the predicate P, then it belongs to the filtered set {x ∈ s | P(x)}.
Finset.mem_biUnion.mpr- If an element belongs to f(a) for some a ∈ s, then it belongs to the union ⋃_{a ∈ s} f(a).
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.
theorem finite_packing_good_of_family_subset {E : Type} [DecidableEq E] (F F' P : Finset (Finset E)) (hFF' : F ⊆ F') (hgood : ∀ p ∈ P, ¬ p ⊆ ((F'.filter (fun t => (t ∩ P.biUnion id).card = 1)).biUnion id)) : ∀ p ∈ P, ¬ p ⊆ ((F.filter (fun t => (t ∩ P.biUnion id).card = 1)).biUnion id) := by intro p hp hsub apply hgood p hp intro e he obtain ⟨t,ht,het⟩ := Finset.mem_biUnion.mp (hsub he) obtain ⟨htF,htcard⟩ := Finset.mem_filter.mp ht exact Finset.mem_biUnion.mpr ⟨t,Finset.mem_filter.mpr ⟨hFF' htF,htcard⟩,het⟩