finite_family_packing_cover_certificate_map
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|$.
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$.
uses
Finset.map_injectiveclassical let fm : Finset α ↪ Finset β := ⟨fun s => s.map f, Finset.map_injective f⟩ let Q := P.map fm let D := C.map f
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\}$.
uses
Finset.mem_map.mp,Finset.mem_image.mprhave 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⟩
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.
uses
Finset.mem_map.mp,congrArg,Finset.disjoint_maphave 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')
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$.
uses
Finset.mem_image.mp,Finset.disjoint_maphave 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
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.
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.
- In the final step, `simpa` automatically simplifies the cardinalities of the mapped finite sets using the fact that embeddings preserve finset cardinality, reducing $|D| \le 2|Q|$ to the assumption $|C| \le 2|P|$.
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_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