AFTD Auto-Formalizing Theoretical Domains

finite_family_disjoint_factor_two_gluing

theoremverified

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

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

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

    lines 9–11

      classical
      obtain ⟨P₁,C₁,⟨hP₁,hpack₁⟩,hc₁,hbound₁⟩ := h₁
      obtain ⟨P₂,C₂,⟨hP₂,hpack₂⟩,hc₂,hbound₂⟩ := h₂
  2. 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.

    line 12

    uses Disjoint.mono

      have hpdisj : Disjoint P₁ P₂ := Disjoint.mono hP₁ hP₂ hF
  3. The 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.

    lines 13–17

    uses Finset.coe_union, Set.pairwise_union_of_symm

      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)
  4. 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₂.

    lines 18–24

    uses Finset.mem_union.mp, Finset.not_disjoint_iff.mp, Finset.not_disjoint_iff.mpr, Finset.mem_union_left, Finset.mem_union_right

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

    line 25

    uses Finset.union_subset_union

      refine ⟨P₁ ∪ P₂,C₁ ∪ C₂,⟨Finset.union_subset_union hP₁ hP₂,hpack⟩,hc,?_⟩
  6. 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₂|.

    lines 26–28

    uses Finset.card_union_le, Finset.card_union_of_disjoint

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

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