AFTD Auto-Formalizing Theoretical Domains

finite_three_set_private_packing_conflict_degree_le_two

theoremverified

For two disjoint-within-family collections of triples P and W, if C meets each P-triple and each W-triple meets C in one point outside the union of P, then each triple in either family intersects at most two triples of the other family.

Statement

theorem finite_three_set_private_packing_conflict_degree_le_two
    {α : Type*} [DecidableEq α] (P W : Finset (Finset α)) (C : Finset α)
    (hPsize : ∀ s ∈ P, s.card = 3) (hWsize : ∀ t ∈ W, t.card = 3)
    (hPdis : (P : Set (Finset α)).Pairwise Disjoint)
    (hWdis : (W : Set (Finset α)).Pairwise Disjoint)
    (hC : ∀ s ∈ P, ¬ Disjoint C s)
    (hprivate : ∀ t ∈ W, (t ∩ C).card = 1 ∧
      Disjoint (t ∩ C) (P.biUnion id)) :
    (∀ s ∈ P, (W.filter fun t => ¬ Disjoint s t).card ≤ 2) ∧
    (∀ t ∈ W, (P.filter fun s => ¬ Disjoint s t).card ≤ 2)
Source
Elementary incidence counting in the triangle packing-cover campaign, related to arXiv:2610.15539, Section 1.
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To bound the number of conflicting triples between P and W by two in both directions, the proof shows that all intersections must occur outside C. For any triple s in P, any conflicting triple t in W must meet s in s \ C because the private point t ∩ C is disjoint from the union of P. Pairwise disjointness of W then allows injecting the conflicting triples into s \ C, whose size is at most 2 since s has size 3 and meets C. Symmetrically, conflicting triples in P inject into t \ C, which has size exactly 2 because |t| = 3 and |t ∩ C| = 1.

  1. If s has size 3 and meets C, then |s \ C| ≤ 2.

    Since s ∩ C ⊆ s, the cardinalities partition as |s \ C| + |s ∩ C| = |s| = 3. Because s ∩ C is nonempty, |s ∩ C| ≥ 1, so linear integer arithmetic yields |s \ C| ≤ 2.

    lines 4–9

    uses Finset.card_sdiff_add_card_eq_card, Finset.inter_subset_left

      have hcard : (s \ C).card + (s ∩ C).card = s.card := by
        have hh := Finset.card_sdiff_add_card_eq_card (s := s ∩ C) (t := s) Finset.inter_subset_left
        rw [show s \ (s ∩ C) = s \ C by ext x; simp] at hh
        exact hh
      have hpos : 0 < (s ∩ C).card := h.card_pos
      omega
  2. If t has size 3 and |t ∩ C| = 1, then |t \ C| = 2.

    As above, |t \ C| + |t ∩ C| = |t| = 3. Substituting |t ∩ C| = 1 immediately gives |t \ C| = 2.

    lines 14–18

    uses Finset.card_sdiff_add_card_eq_card, Finset.inter_subset_left

      have hcard : (t \ C).card + (t ∩ C).card = t.card := by
        have hh := Finset.card_sdiff_add_card_eq_card (s := t ∩ C) (t := t) Finset.inter_subset_left
        rw [show t \ (t ∩ C) = t \ C by ext x; simp] at hh
        exact hh
      omega
  3. The choice function f maps the conflicting elements of X into z \ C.

    Let D be the subcollection of sets in X that intersect z. For each t ∈ D, the hypothesis hex guarantees an element in (z \ C) ∩ t; defining f(t) by choosing such an element, f sends every t ∈ D into z \ C.

    lines 25–39

    uses Finset.filter_subset, Finset.mem_filter.mp, dif_pos, Classical.choose_spec

      classical
      let D := X.filter (fun t => ¬ Disjoint z t)
      have hDsub : D ⊆ X := Finset.filter_subset _ _
      let f : Finset α → α := fun t =>
        if h : ∃ x, x ∈ z \ C ∧ x ∈ t then Classical.choose h else a0
      have hf_maps : Set.MapsTo f ↑D ↑(z \ C) := by
        intro t ht
        have htX : t ∈ X := hDsub ht
        have hconf : ¬ Disjoint z t := (Finset.mem_filter.mp ht).2
        have h := hex t htX hconf
        have hft : f t = Classical.choose h := by
          dsimp [f]
          rw [dif_pos h]
        rw [hft]
        exact (Classical.choose_spec h).1
  4. The map f is injective on D, so |D| ≤ |z \ C|.

    If f(t₁) = f(t₂) = x, then x ∈ t₁ and x ∈ t₂. Since X is pairwise disjoint, t₁ and t₂ cannot share an element unless t₁ = t₂. Hence f is injective on D, and the cardinality of D is at most |z \ C|.

    lines 40–60

    uses Finset.filter_subset, Finset.mem_filter.mp, dif_pos, Classical.choose_spec, Finset.disjoint_left.mp, Finset.card_le_card_of_injOn

      have hf_inj : Set.InjOn f ↑D := by
        intro t1 ht1 t2 ht2 heq
        by_contra hne
        have ht1X : t1 ∈ X := hDsub ht1
        have ht2X : t2 ∈ X := hDsub ht2
        have hconf1 : ¬ Disjoint z t1 := (Finset.mem_filter.mp ht1).2
        have hconf2 : ¬ Disjoint z t2 := (Finset.mem_filter.mp ht2).2
        have h1 := hex t1 ht1X hconf1
        have h2 := hex t2 ht2X hconf2
        have hf1 : f t1 = Classical.choose h1 := by dsimp [f]; rw [dif_pos h1]
        have hf2 : f t2 = Classical.choose h2 := by dsimp [f]; rw [dif_pos h2]
        have hx1 : Classical.choose h1 ∈ t1 := (Classical.choose_spec h1).2
        have hx2 : Classical.choose h2 ∈ t2 := (Classical.choose_spec h2).2
        have hxmem2 : Classical.choose h1 ∈ t2 := by
          rw [← hf1, heq, hf2]
          exact hx2
        have hdis : Disjoint t1 t2 := hXdis ht1X ht2X hne
        exact (Finset.disjoint_left.mp hdis hx1 hxmem2).elim
      calc
        (X.filter (fun t => ¬ Disjoint z t)).card = D.card := rfl
        _ ≤ (z \ C).card := Finset.card_le_card_of_injOn f hf_maps hf_inj
  5. For each s ∈ P, any t ∈ W intersecting s intersects s outside C.

    Fix s ∈ P and suppose t ∈ W intersects s at a point x. If x were in C, then x would belong to t ∩ C, and since x ∈ s, also to the union of P. But t ∩ C is disjoint from the union of P, a contradiction. Thus x ∉ C, meaning x ∈ (s \ C) ∩ t.

    lines 72–92

    uses Finset.card_pos.mp, Finset.not_disjoint_iff_nonempty_inter.mp, Finset.mem_inter, Finset.mem_sdiff, Finset.mem_biUnion.mpr, Finset.disjoint_left.mp

      classical
      constructor
      · intro s hsP
        let a0 : α := Classical.choose (Finset.card_pos.mp (by
          rw [hPsize s hsP]
          norm_num))
        have hex : ∀ t ∈ W, ¬ Disjoint s t → ∃ x, x ∈ s \ C ∧ x ∈ t := by
          intro t htW hconf
          have hnon : (s ∩ t).Nonempty := Finset.not_disjoint_iff_nonempty_inter.mp hconf
          obtain ⟨x, hx⟩ := hnon
          rw [Finset.mem_inter] at hx
          refine ⟨x, ?_, hx.2⟩
          rw [Finset.mem_sdiff]
          refine ⟨hx.1, ?_⟩
          intro hxC
          have hxTC : x ∈ t ∩ C := by
            rw [Finset.mem_inter]
            exact ⟨hx.2, hxC⟩
          have hxUnion : x ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨s, hsP, hx.1⟩
          have hdis := (hprivate t htW).2
          exact (Finset.disjoint_left.mp hdis hxTC hxUnion).elim
  6. For each s ∈ P, at most 2 triples in W intersect s.

    By the injection lemma with X = W and z = s, the number of triples in W intersecting s is at most |s \ C|. Since s meets C and has size 3, |s \ C| ≤ 2 by our first helper lemma, giving the upper bound 2.

    lines 93–100

    uses finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff, Finset.not_disjoint_iff_nonempty_inter.mp, Finset.inter_comm, finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_le_two, le_trans

        have hle := finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff
          a0 hWdis hex
        have hnonC : (s ∩ C).Nonempty := by
          have h := Finset.not_disjoint_iff_nonempty_inter.mp (hC s hsP)
          simpa [Finset.inter_comm] using h
        have htarget : (s \ C).card ≤ 2 :=
          finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_le_two (hPsize s hsP) hnonC
        exact le_trans hle htarget
  7. For each t ∈ W, any s ∈ P intersecting t intersects t outside C.

    Fix t ∈ W and suppose s ∈ P intersects t at a point x. As before, if x ∈ C then x ∈ t ∩ C and x ∈ s ⊆ ⋃ P, contradicting the disjointness of t ∩ C and ⋃ P. Therefore x ∉ C, so x ∈ (t \ C) ∩ s.

    lines 101–119

    uses Finset.card_pos.mp, Finset.not_disjoint_iff_nonempty_inter.mp, Finset.mem_inter, Finset.mem_sdiff, Finset.mem_biUnion.mpr, Finset.disjoint_left.mp

      · intro t htW
        let a0 : α := Classical.choose (Finset.card_pos.mp (by
          rw [hWsize t htW]
          norm_num))
        have hex : ∀ s ∈ P, ¬ Disjoint t s → ∃ x, x ∈ t \ C ∧ x ∈ s := by
          intro s hsP hconf
          have hnon : (t ∩ s).Nonempty := Finset.not_disjoint_iff_nonempty_inter.mp hconf
          obtain ⟨x, hx⟩ := hnon
          rw [Finset.mem_inter] at hx
          refine ⟨x, ?_, hx.2⟩
          rw [Finset.mem_sdiff]
          refine ⟨hx.1, ?_⟩
          intro hxC
          have hxTC : x ∈ t ∩ C := by
            rw [Finset.mem_inter]
            exact ⟨hx.1, hxC⟩
          have hxUnion : x ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨s, hsP, hx.2⟩
          have hdis := (hprivate t htW).2
          exact (Finset.disjoint_left.mp hdis hxTC hxUnion).elim
  8. For each t ∈ W, at most 2 triples in P intersect t.

    By the injection lemma with X = P and z = t, the number of triples in P intersecting t is at most |t \ C|. Symmetry of disjointness allows rewriting the filter condition, and since |t| = 3 and |t ∩ C| = 1, |t \ C| = 2 by our second helper lemma. Transitivity completes the proof.

    lines 120–131

    uses finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff, Finset.filter_congr, not_congr, disjoint_comm, finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_eq_two, le_trans, le_of_eq

        have hle := finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff
          a0 hPdis hex
        have hfilter : (P.filter fun s => ¬ Disjoint s t) =
            (P.filter fun s => ¬ Disjoint t s) := by
          apply Finset.filter_congr
          intro s hs
          exact not_congr (disjoint_comm (a := s) (b := t))
        rw [hfilter]
        have htarget : (t \ C).card = 2 :=
          finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_eq_two
            (hWsize t htW) (hprivate t htW).1
        exact le_trans hle (le_of_eq htarget)
Finset.card_sdiff_add_card_eq_card
For finite sets s ⊆ t, |t \ s| + |s| = |t|.
Finset.inter_subset_left
For any sets s₁ and s₂, the intersection s₁ ∩ s₂ is a subset of s₁.
Finset.filter_subset
Filtering a finite set by a predicate produces a subset of the original set.
dif_pos
If a condition c is true, the dependent if-then-else evaluates to the then-branch.
Classical.choose_spec
The witness selected by Classical.choose satisfies the existence predicate.
Finset.mem_filter.mp
An element of a filtered finite set belongs to the base set and satisfies the filter condition.
Finset.disjoint_left.mp
If two sets are disjoint, any element of the first does not belong to the second.
Finset.card_le_card_of_injOn
If an injective function maps a finite set s into a finite set t, then |s| ≤ |t|.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.not_disjoint_iff_nonempty_inter.mp
If two finite sets are not disjoint, their intersection is nonempty.
Finset.mem_inter
An element belongs to the intersection of two sets if and only if it belongs to both sets.
Finset.mem_sdiff
An element belongs to the set difference s \ t if and only if it belongs to s and not to t.
Finset.mem_biUnion.mpr
An element belongs to the union of a family of sets if it belongs to at least one set in the family.
Finset.inter_comm
Intersection of finite sets is commutative.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Finset.filter_congr
If two predicates are equivalent on every element of a set, filtering by them yields identical subsets.
not_congr
Logical equivalence between two propositions implies equivalence of their negations.
disjoint_comm
Disjointness of sets is symmetric.
le_of_eq
Equality between numbers implies the corresponding non-strict inequality.
finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_le_two
A 3-element set meeting C has at most 2 elements outside C.
finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_eq_two
A 3-element set meeting C in exactly 1 element has exactly 2 elements outside C.
finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff
For a pairwise disjoint collection X, if every set in X intersecting z meets z \ C, then the number of such intersecting sets is at most |z \ C|.

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

private lemma finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_le_two    {α : Type*} [DecidableEq α] {s C : Finset α}    (hs : s.card = 3) (h : (s ∩ C).Nonempty) : (s \ C).card ≤ 2 := by  have hcard : (s \ C).card + (s ∩ C).card = s.card := by    have hh := Finset.card_sdiff_add_card_eq_card (s := s ∩ C) (t := s) Finset.inter_subset_left    rw [show s \ (s ∩ C) = s \ C by ext x; simp] at hh    exact hh  have hpos : 0 < (s ∩ C).card := h.card_pos  omegaprivate lemma finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_eq_two    {α : Type*} [DecidableEq α] {t C : Finset α}    (ht : t.card = 3) (h : (t ∩ C).card = 1) : (t \ C).card = 2 := by  have hcard : (t \ C).card + (t ∩ C).card = t.card := by    have hh := Finset.card_sdiff_add_card_eq_card (s := t ∩ C) (t := t) Finset.inter_subset_left    rw [show t \ (t ∩ C) = t \ C by ext x; simp] at hh    exact hh  omegaprivate lemma finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff    {α : Type*} [DecidableEq α] {X : Finset (Finset α)} {z C : Finset α}    (a0 : α) (hXdis : (X : Set (Finset α)).Pairwise Disjoint)    (hex : ∀ t ∈ X, ¬ Disjoint z t → ∃ x, x ∈ z \ C ∧ x ∈ t) :    (X.filter (fun t => ¬ Disjoint z t)).card ≤ (z \ C).card := by  classical  let D := X.filter (fun t => ¬ Disjoint z t)  have hDsub : D ⊆ X := Finset.filter_subset _ _  let f : Finset α → α := fun t =>    if h : ∃ x, x ∈ z \ C ∧ x ∈ t then Classical.choose h else a0  have hf_maps : Set.MapsTo f ↑D ↑(z \ C) := by    intro t ht    have htX : t ∈ X := hDsub ht    have hconf : ¬ Disjoint z t := (Finset.mem_filter.mp ht).2    have h := hex t htX hconf    have hft : f t = Classical.choose h := by      dsimp [f]      rw [dif_pos h]    rw [hft]    exact (Classical.choose_spec h).1  have hf_inj : Set.InjOn f ↑D := by    intro t1 ht1 t2 ht2 heq    by_contra hne    have ht1X : t1 ∈ X := hDsub ht1    have ht2X : t2 ∈ X := hDsub ht2    have hconf1 : ¬ Disjoint z t1 := (Finset.mem_filter.mp ht1).2    have hconf2 : ¬ Disjoint z t2 := (Finset.mem_filter.mp ht2).2    have h1 := hex t1 ht1X hconf1    have h2 := hex t2 ht2X hconf2    have hf1 : f t1 = Classical.choose h1 := by dsimp [f]; rw [dif_pos h1]    have hf2 : f t2 = Classical.choose h2 := by dsimp [f]; rw [dif_pos h2]    have hx1 : Classical.choose h1 ∈ t1 := (Classical.choose_spec h1).2    have hx2 : Classical.choose h2 ∈ t2 := (Classical.choose_spec h2).2    have hxmem2 : Classical.choose h1 ∈ t2 := by      rw [← hf1, heq, hf2]      exact hx2    have hdis : Disjoint t1 t2 := hXdis ht1X ht2X hne    exact (Finset.disjoint_left.mp hdis hx1 hxmem2).elim  calc    (X.filter (fun t => ¬ Disjoint z t)).card = D.card := rfl    _ ≤ (z \ C).card := Finset.card_le_card_of_injOn f hf_maps hf_injtheorem finite_three_set_private_packing_conflict_degree_le_two    {α : Type*} [DecidableEq α] (P W : Finset (Finset α)) (C : Finset α)    (hPsize : ∀ s ∈ P, s.card = 3) (hWsize : ∀ t ∈ W, t.card = 3)    (hPdis : (P : Set (Finset α)).Pairwise Disjoint)    (hWdis : (W : Set (Finset α)).Pairwise Disjoint)    (hC : ∀ s ∈ P, ¬ Disjoint C s)    (hprivate : ∀ t ∈ W, (t ∩ C).card = 1 ∧      Disjoint (t ∩ C) (P.biUnion id)) :    (∀ s ∈ P, (W.filter fun t => ¬ Disjoint s t).card ≤ 2) ∧    (∀ t ∈ W, (P.filter fun s => ¬ Disjoint s t).card ≤ 2) := by  classical  constructor  · intro s hsP    let a0 : α := Classical.choose (Finset.card_pos.mp (by      rw [hPsize s hsP]      norm_num))    have hex : ∀ t ∈ W, ¬ Disjoint s t → ∃ x, x ∈ s \ C ∧ x ∈ t := by      intro t htW hconf      have hnon : (s ∩ t).Nonempty := Finset.not_disjoint_iff_nonempty_inter.mp hconf      obtain ⟨x, hx⟩ := hnon      rw [Finset.mem_inter] at hx      refine ⟨x, ?_, hx.2⟩      rw [Finset.mem_sdiff]      refine ⟨hx.1, ?_⟩      intro hxC      have hxTC : x ∈ t ∩ C := by        rw [Finset.mem_inter]        exact ⟨hx.2, hxC⟩      have hxUnion : x ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨s, hsP, hx.1⟩      have hdis := (hprivate t htW).2      exact (Finset.disjoint_left.mp hdis hxTC hxUnion).elim    have hle := finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff      a0 hWdis hex    have hnonC : (s ∩ C).Nonempty := by      have h := Finset.not_disjoint_iff_nonempty_inter.mp (hC s hsP)      simpa [Finset.inter_comm] using h    have htarget : (s \ C).card ≤ 2 :=      finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_le_two (hPsize s hsP) hnonC    exact le_trans hle htarget  · intro t htW    let a0 : α := Classical.choose (Finset.card_pos.mp (by      rw [hWsize t htW]      norm_num))    have hex : ∀ s ∈ P, ¬ Disjoint t s → ∃ x, x ∈ t \ C ∧ x ∈ s := by      intro s hsP hconf      have hnon : (t ∩ s).Nonempty := Finset.not_disjoint_iff_nonempty_inter.mp hconf      obtain ⟨x, hx⟩ := hnon      rw [Finset.mem_inter] at hx      refine ⟨x, ?_, hx.2⟩      rw [Finset.mem_sdiff]      refine ⟨hx.1, ?_⟩      intro hxC      have hxTC : x ∈ t ∩ C := by        rw [Finset.mem_inter]        exact ⟨hx.1, hxC⟩      have hxUnion : x ∈ P.biUnion id := Finset.mem_biUnion.mpr ⟨s, hsP, hx.2⟩      have hdis := (hprivate t htW).2      exact (Finset.disjoint_left.mp hdis hxTC hxUnion).elim    have hle := finite_three_set_private_packing_conflict_degree_le_two_card_filter_not_disjoint_le_card_sdiff      a0 hPdis hex    have hfilter : (P.filter fun s => ¬ Disjoint s t) =        (P.filter fun s => ¬ Disjoint t s) := by      apply Finset.filter_congr      intro s hs      exact not_congr (disjoint_comm (a := s) (b := t))    rw [hfilter]    have htarget : (t \ C).card = 2 :=      finite_three_set_private_packing_conflict_degree_le_two_sdiff_card_eq_two        (hWsize t htW) (hprivate t htW).1    exact le_trans hle (le_of_eq htarget)
See it in the graphDiscuss this resultChallenge it