AFTD Auto-Formalizing Theoretical Domains

finite_packing_good_of_family_subset

theoremverified

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

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

    lines 5–6

      intro p hp hsub
      apply hgood p hp
  2. 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.

    lines 7–10

    uses Finset.mem_biUnion.mp, Finset.mem_filter.mp, Finset.mem_filter.mpr, Finset.mem_biUnion.mpr

      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⟩
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

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