AFTD Auto-Formalizing Theoretical Domains

finite_family_packing_cover_certificate_map

theoremverified

An injective relabeling transports finite-family disjoint packings and point covers, preserving the factor-two certificate.

Statement

theorem finite_family_packing_cover_certificate_map {α β : Type*} [DecidableEq α] [DecidableEq β]
    (f : α ↪ β) (F P : Finset (Finset α)) (C : Finset α)
    (hsub : P ⊆ F) (hpack : (P : Set (Finset α)).Pairwise Disjoint)
    (hcover : ∀ A ∈ F, ¬ Disjoint A C) (hbound : C.card ≤ 2 * P.card) :
    ∃ Q : Finset (Finset β), ∃ D : Finset β,
      Q ⊆ F.image (fun s => s.map f) ∧ (Q : Set (Finset β)).Pairwise Disjoint ∧
      (∀ B ∈ F.image (fun s => s.map f), ¬ Disjoint B D) ∧ D.card ≤ 2 * Q.card
Source
Injective relabeling for the two-vertex separator route of the triangle packing campaign.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To transport the packing and covering certificate along an injection $f : \alpha \hookrightarrow \beta$, the candidate packing $Q$ and cover $D$ are constructed as the images of $P$ and $C$ under $f$. Because $f$ is injective, it preserves both disjointness and set cardinalities. Thus, $Q$ remains a pairwise disjoint subcollection of the mapped family, $D$ intersects every element of the mapped family, and the certificate inequality $|D| \le 2|Q|$ is preserved from $|C| \le 2|P|$.

  1. Define the candidate packing Q and cover D by pushing forward P and C along f.

    Using `Finset.map_injective`, the embedding $f : \alpha \hookrightarrow \beta$ induces an embedding $fm$ from finite sets of $\alpha$ to finite sets of $\beta$ by mapping each set elementwise. We define the packing $Q$ to be the image of $P$ under $fm$ and the hitting set $D$ to be the image of $C$ under $f$.

    lines 8–11

    uses Finset.map_injective

      classical
      let fm : Finset α ↪ Finset β := ⟨fun s => s.map f, Finset.map_injective f⟩
      let Q := P.map fm
      let D := C.map f
  2. Q is a subcollection of the mapped family of sets.

    Given any set $A \in Q$, by `Finset.mem_map.mp` it is of the form $f(s)$ for some $s \in P$. Since $P \subseteq F$, we have $s \in F$, so by `Finset.mem_image.mpr`, $A$ belongs to the image family $\{f(s) : s \in F\}$.

    lines 12–15

    uses Finset.mem_map.mp, Finset.mem_image.mpr

      have hQsub : Q ⊆ F.image (fun s => s.map f) := by
        intro A hA
        obtain ⟨s,hs,rfl⟩ := Finset.mem_map.mp hA
        exact Finset.mem_image.mpr ⟨s,hsub hs,rfl⟩
  3. The sets in Q are pairwise disjoint.

    Let $A, B \in Q$ with $A \neq B$. By `Finset.mem_map.mp`, $A = f(a)$ and $B = f(b)$ for some $a, b \in P$. If $a = b$, applying $fm$ via `congrArg` would give $A = B$, so $a \neq b$. Since $P$ is pairwise disjoint, $a$ and $b$ are disjoint. Because $f$ is injective, `Finset.disjoint_map` implies that their images $f(a)$ and $f(b)$ are disjoint.

    lines 16–22

    uses Finset.mem_map.mp, congrArg, Finset.disjoint_map

      have hQpack : (Q : Set (Finset β)).Pairwise Disjoint := by
        intro A hA B hB hne
        obtain ⟨a,ha,rfl⟩ := Finset.mem_map.mp hA
        obtain ⟨b,hb,rfl⟩ := Finset.mem_map.mp hB
        have hne' : a ≠ b := by intro h; exact hne (congrArg fm h)
        change Disjoint (a.map f) (b.map f)
        exact (Finset.disjoint_map f).mpr (hpack ha hb hne')
  4. The set D intersects every set in the mapped family.

    Assume for contradiction that some set $B$ in the mapped family is disjoint from $D$. By `Finset.mem_image.mp`, $B = f(a)$ for some $a \in F$. Since $f(a)$ and $D = f(C)$ are disjoint, `Finset.disjoint_map` implies $a$ and $C$ are disjoint, contradicting the hypothesis that $C$ intersects every set in $F$.

    lines 23–27

    uses Finset.mem_image.mp, Finset.disjoint_map

      have hQcover : ∀ B ∈ F.image (fun s => s.map f), ¬ Disjoint B D := by
        intro B hB hdisj
        obtain ⟨a,ha,rfl⟩ := Finset.mem_image.mp hB
        apply hcover a ha
        exact (Finset.disjoint_map f).mp hdisj
  5. The witnesses Q and D satisfy all conditions, concluding the proof. automation

    We supply $Q$ and $D$ as witnesses. The subcollection, disjoint packing, and hitting set properties were proven above. The cardinality bound $|D| \le 2|Q|$ simplifies to $|C| \le 2|P|$ because injective maps preserve finset cardinalities, which holds directly by assumption.

    lines 28–29

      refine ⟨Q,D,hQsub,hQpack,hQcover,?_⟩
      simpa [Q,D] using hbound
congrArg
Applying a function to equal inputs yields equal outputs.
Finset.disjoint_map
Two finite sets are disjoint if and only if their images under an injective function are disjoint.
Finset.mem_image.mpr
An element belongs to the image of a finite set under a function if it is the image of some element in that set.
Finset.mem_image.mp
An element in the image of a finite set under a function is the image of some element of that set.
Finset.mem_map.mp
An element in the image of a finite set under an embedding is the image of some element of that set.
Finset.map_injective
Mapping finite sets under an injective function is an injective operation on finite sets.

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_family_packing_cover_certificate_map {α β : Type*} [DecidableEq α] [DecidableEq β]    (f : α ↪ β) (F P : Finset (Finset α)) (C : Finset α)    (hsub : P ⊆ F) (hpack : (P : Set (Finset α)).Pairwise Disjoint)    (hcover : ∀ A ∈ F, ¬ Disjoint A C) (hbound : C.card ≤ 2 * P.card) :    ∃ Q : Finset (Finset β), ∃ D : Finset β,      Q ⊆ F.image (fun s => s.map f) ∧ (Q : Set (Finset β)).Pairwise Disjoint ∧      (∀ B ∈ F.image (fun s => s.map f), ¬ Disjoint B D) ∧ D.card ≤ 2 * Q.card := by  classical  let fm : Finset α ↪ Finset β := ⟨fun s => s.map f, Finset.map_injective f⟩  let Q := P.map fm  let D := C.map f  have hQsub : Q ⊆ F.image (fun s => s.map f) := by    intro A hA    obtain ⟨s,hs,rfl⟩ := Finset.mem_map.mp hA    exact Finset.mem_image.mpr ⟨s,hsub hs,rfl⟩  have hQpack : (Q : Set (Finset β)).Pairwise Disjoint := by    intro A hA B hB hne    obtain ⟨a,ha,rfl⟩ := Finset.mem_map.mp hA    obtain ⟨b,hb,rfl⟩ := Finset.mem_map.mp hB    have hne' : a ≠ b := by intro h; exact hne (congrArg fm h)    change Disjoint (a.map f) (b.map f)    exact (Finset.disjoint_map f).mpr (hpack ha hb hne')  have hQcover : ∀ B ∈ F.image (fun s => s.map f), ¬ Disjoint B D := by    intro B hB hdisj    obtain ⟨a,ha,rfl⟩ := Finset.mem_image.mp hB    apply hcover a ha    exact (Finset.disjoint_map f).mp hdisj  refine ⟨Q,D,hQsub,hQpack,hQcover,?_⟩  simpa [Q,D] using hbound
See it in the graphDiscuss this resultChallenge it