finite_family_disjoint_factor_two_gluing
Factor-two packing-cover certificates combine for disjoint finite families when every member from one family is disjoint from every member of the other.
Statement
theorem finite_family_disjoint_factor_two_gluing {α : Type*} [DecidableEq α] (F₁ F₂ : Finset (Finset α)) (hF : Disjoint F₁ F₂) (hcross : ∀ A ∈ F₁, ∀ B ∈ F₂, Disjoint A B) (h₁ : ∃ P C, finite_family_packing_is_disjoint F₁ P ∧ finite_family_point_cover F₁ C ∧ C.card ≤ 2 * P.card) (h₂ : ∃ P C, finite_family_packing_is_disjoint F₂ P ∧ finite_family_point_cover F₂ C ∧ C.card ≤ 2 * P.card) : ∃ P C, finite_family_packing_is_disjoint (F₁ ∪ F₂) P ∧ finite_family_point_cover (F₁ ∪ F₂) C ∧ C.card ≤ 2 * P.card
- Source
- Disjoint-side case of the published separator reduction, https://www.cs.tau.ac.il/~krivelev/2.pdf, Lemma 5.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- finite_family_packing_is_disjointA subfamily is a packing when its distinct members are disjoint.
- finite_family_point_coverA set of points meets every member of a finite family.
The proof, explained
The proof glues the certificates by taking the union of the packings P = P₁ ∪ P₂ and the union of the covers C = C₁ ∪ C₂. Cross-disjointness between F₁ and F₂ guarantees that elements from P₁ and P₂ are mutually disjoint, making P a valid disjoint packing. Finally, subadditivity of cover size and additivity of packing size (since P₁ and P₂ are disjoint) preserve the factor-two bound |C| ≤ 2|P|.
Extract factor-two packing-cover pairs for F₁ and F₂.
Using classical logic, unpack the existential hypotheses h₁ and h₂ to obtain pairwise disjoint packings P₁ ⊆ F₁ and P₂ ⊆ F₂, point covers C₁ and C₂, and the size bounds |C₁| ≤ 2|P₁| and |C₂| ≤ 2|P₂|.
classical obtain ⟨P₁,C₁,⟨hP₁,hpack₁⟩,hc₁,hbound₁⟩ := h₁ obtain ⟨P₂,C₂,⟨hP₂,hpack₂⟩,hc₂,hbound₂⟩ := h₂
The packings P₁ and P₂ are disjoint as families.
Because P₁ ⊆ F₁ and P₂ ⊆ F₂, and the ambient families F₁ and F₂ are disjoint, monotonicity of disjointness shows that P₁ and P₂ are disjoint.
uses
Disjoint.monohave hpdisj : Disjoint P₁ P₂ := Disjoint.mono hP₁ hP₂ hFThe union P₁ ∪ P₂ is a pairwise disjoint family of sets.
By Finset.coe_union and Set.pairwise_union_of_symm, the union P₁ ∪ P₂ is pairwise disjoint if both subfamilies are pairwise disjoint and all cross-pairs are disjoint. The internal disjointness is already known, and for any A ∈ P₁ ⊆ F₁ and B ∈ P₂ ⊆ F₂, the sets A and B are disjoint by the cross-disjointness assumption hcross.
uses
Finset.coe_union,Set.pairwise_union_of_symmhave hpack : ((P₁ ∪ P₂ : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by rw [Finset.coe_union, Set.pairwise_union_of_symm] refine ⟨hpack₁,hpack₂,?_⟩ intro A hA B hB _ exact hcross A (hP₁ hA) B (hP₂ hB)
The union C₁ ∪ C₂ is a point cover for F₁ ∪ F₂.
Every set A ∈ F₁ ∪ F₂ belongs to F₁ or F₂. If A ∈ F₁, then because C₁ is a cover for F₁, some element x lies in both A and C₁, and hence in A and C₁ ∪ C₂; the case A ∈ F₂ is symmetric with C₂. In both cases, A intersects C₁ ∪ C₂.
uses
Finset.mem_union.mp,Finset.not_disjoint_iff.mp,Finset.not_disjoint_iff.mpr,Finset.mem_union_left,Finset.mem_union_righthave hc : finite_family_point_cover (F₁ ∪ F₂) (C₁ ∪ C₂) := by intro A hA rcases Finset.mem_union.mp hA with hA | hA · obtain ⟨x,hxA,hxC⟩ := Finset.not_disjoint_iff.mp (hc₁ A hA) exact Finset.not_disjoint_iff.mpr ⟨x,hxA,Finset.mem_union_left _ hxC⟩ · obtain ⟨x,hxA,hxC⟩ := Finset.not_disjoint_iff.mp (hc₂ A hA) exact Finset.not_disjoint_iff.mpr ⟨x,hxA,Finset.mem_union_right _ hxC⟩
P₁ ∪ P₂ and C₁ ∪ C₂ witness the packing and covering requirements for F₁ ∪ F₂, leaving only the size bound.
Propose P₁ ∪ P₂ and C₁ ∪ C₂ as witnesses. The union P₁ ∪ P₂ is a subset of F₁ ∪ F₂ by Finset.union_subset_union and has already been shown pairwise disjoint. Combined with the point-cover property established for C₁ ∪ C₂, it remains only to verify the cardinality inequality.
uses
Finset.union_subset_unionrefine ⟨P₁ ∪ P₂,C₁ ∪ C₂,⟨Finset.union_subset_union hP₁ hP₂,hpack⟩,hc,?_⟩The combined cover satisfies the factor-two cardinality bound |C₁ ∪ C₂| ≤ 2|P₁ ∪ P₂|. automation
Subadditivity (Finset.card_union_le) gives |C₁ ∪ C₂| ≤ |C₁| + |C₂|, while disjointness of P₁ and P₂ (Finset.card_union_of_disjoint) gives |P₁ ∪ P₂| = |P₁| + |P₂|. Linear arithmetic (omega) then deduces |C₁ ∪ C₂| ≤ 2|P₁ ∪ P₂| from |C₁| ≤ 2|P₁| and |C₂| ≤ 2|P₂|.
uses
Finset.card_union_le,Finset.card_union_of_disjointhave hcard := Finset.card_union_le C₁ C₂ rw [Finset.card_union_of_disjoint hpdisj] omega
Disjoint.mono- Disjointness is antimonotone: if a ≤ b, c ≤ d, and b is disjoint from d, then a is disjoint from c.
Finset.coe_union- The coercion of a union of finite sets to a set equals the union of their set coercions.
Set.pairwise_union_of_symm- The union of two sets is pairwise disjoint if each set is pairwise disjoint and every element of the first is disjoint from every element of the second.
Finset.mem_union.mp- An element of the union of two finite sets belongs to the first set or the second set.
Finset.not_disjoint_iff.mp- Two finite sets that are not disjoint share at least one element.
Finset.not_disjoint_iff.mpr- Two finite sets that share an element are not disjoint.
Finset.mem_union_left- An element of a finite set is also an element of its union with another finite set.
Finset.mem_union_right- An element of the second finite set is an element of the union of the two sets.
Finset.union_subset_union- If s ⊆ u and t ⊆ v, then s ∪ t ⊆ u ∪ v.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets equals the sum of their cardinalities.
- The final inequality bounding the size of the combined cover by twice the size of the combined packing is discharged automatically by the linear integer arithmetic tactic `omega`.
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_disjoint_factor_two_gluing {α : Type*} [DecidableEq α] (F₁ F₂ : Finset (Finset α)) (hF : Disjoint F₁ F₂) (hcross : ∀ A ∈ F₁, ∀ B ∈ F₂, Disjoint A B) (h₁ : ∃ P C, finite_family_packing_is_disjoint F₁ P ∧ finite_family_point_cover F₁ C ∧ C.card ≤ 2 * P.card) (h₂ : ∃ P C, finite_family_packing_is_disjoint F₂ P ∧ finite_family_point_cover F₂ C ∧ C.card ≤ 2 * P.card) : ∃ P C, finite_family_packing_is_disjoint (F₁ ∪ F₂) P ∧ finite_family_point_cover (F₁ ∪ F₂) C ∧ C.card ≤ 2 * P.card := by classical obtain ⟨P₁,C₁,⟨hP₁,hpack₁⟩,hc₁,hbound₁⟩ := h₁ obtain ⟨P₂,C₂,⟨hP₂,hpack₂⟩,hc₂,hbound₂⟩ := h₂ have hpdisj : Disjoint P₁ P₂ := Disjoint.mono hP₁ hP₂ hF have hpack : ((P₁ ∪ P₂ : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by rw [Finset.coe_union, Set.pairwise_union_of_symm] refine ⟨hpack₁,hpack₂,?_⟩ intro A hA B hB _ exact hcross A (hP₁ hA) B (hP₂ hB) have hc : finite_family_point_cover (F₁ ∪ F₂) (C₁ ∪ C₂) := by intro A hA rcases Finset.mem_union.mp hA with hA | hA · obtain ⟨x,hxA,hxC⟩ := Finset.not_disjoint_iff.mp (hc₁ A hA) exact Finset.not_disjoint_iff.mpr ⟨x,hxA,Finset.mem_union_left _ hxC⟩ · obtain ⟨x,hxA,hxC⟩ := Finset.not_disjoint_iff.mp (hc₂ A hA) exact Finset.not_disjoint_iff.mpr ⟨x,hxA,Finset.mem_union_right _ hxC⟩ refine ⟨P₁ ∪ P₂,C₁ ∪ C₂,⟨Finset.union_subset_union hP₁ hP₂,hpack⟩,hc,?_⟩ have hcard := Finset.card_union_le C₁ C₂ rw [Finset.card_union_of_disjoint hpdisj] omega