AFTD Auto-Formalizing Theoretical Domains

finite_three_set_stable_nonextendable_triple_patterns

theoremverified

In a finite family of three-element sets where every point can be omitted by some maximum packing, if a triple belongs to no maximum packing, then for each of its points there is a maximum packing omitting that point and covering both of the other two.

Statement

theorem finite_three_set_stable_nonextendable_triple_patterns
    {α : Type*} [DecidableEq α] (F : Finset (Finset α)) (k : ℕ)
    (hthree : ∀ t ∈ F, t.card = 3)
    (hmax : ∀ P : Finset (Finset α), P ⊆ F →
      (P : Set (Finset α)).Pairwise Disjoint → P.card ≤ k)
    (hstable : ∀ x ∈ F.biUnion id, ∃ P : Finset (Finset α),
      P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧
      ∀ s ∈ P, x ∉ s)
    (T : Finset α) (hTF : T ∈ F)
    (hnonextendable : ∀ P : Finset (Finset α), P ⊆ F →
      (P : Set (Finset α)).Pairwise Disjoint → P.card = k → T ∉ P) :
    ∀ x ∈ T, ∃ P : Finset (Finset α),
      P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧
      (∀ s ∈ P, x ∉ s) ∧
      (∀ y ∈ T, y ≠ x → ∃ s ∈ P, y ∈ s)
Source
Elementary packing exchange in the triangle packing-cover campaign, related to arXiv:2610.15539, Section 1.
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

Given a triple T ∈ F and a point x ∈ T, stability yields a maximum packing P of size k omitting x. To show that P covers the other two points of T, assume for contradiction that some y ∈ T \\ {x} is also omitted by all sets in P. Because any set in P intersecting T can only do so at the unique remaining point T \\ {x, y}, at most one set in P intersects T. But augmenting P by T (if no set intersects T) or replacing that single set with T (if one set intersects T) produces a packing containing T of size k + 1 or k, contradicting either the maximality of k or the assumption that T belongs to no maximum packing.

  1. There exists a maximum packing P of size k that omits the chosen element x ∈ T.

    Given x ∈ T, since T ∈ F is a 3-element set, x belongs to the union of F. By the stability hypothesis (hstable), there exists a pairwise disjoint subcollection P ⊆ F of size k that omits x. It remains to show that P covers every other element y ∈ T with y ≠ x.

    lines 16–21

    uses mem_biUnion

      open Finset in
      intro x hxT
      have hTcard : T.card = 3 := hthree T hTF
      have hx_biUnion : x ∈ F.biUnion id := mem_biUnion.2 ⟨T, hTF, hxT⟩
      obtain ⟨P, hPF, hPdisj, hPcard, hPnotx⟩ := hstable x hx_biUnion
      refine ⟨P, hPF, hPdisj, hPcard, hPnotx, ?_⟩
  2. Suppose for contradiction that some other element y ∈ T \\ {x} is not covered by any set in P.

    We assume the negation of the remaining claim, which provides an element y ∈ T with y ≠ x such that no set in P contains y.

    lines 22–23

      by_contra! hmiss
      obtain ⟨y, hyT, hyne, hPnoty⟩ := hmiss
  3. At most one set in P intersects T.

    Let C be the subcollection of sets in P that intersect T. For any two sets a, b ∈ C, their intersections with T are nonempty. Any element za ∈ a ∩ T cannot be x (since P omits x) and cannot be y (by the contradiction assumption), so za ∈ T \\ {x, y}. Similarly, any zb ∈ b ∩ T belongs to T \\ {x, y}. Since |T| = 3 and x ≠ y, the difference T \\ {x, y} has cardinality 3 - 2 = 1, meaning it contains a unique element z. Thus za = zb = z, which implies z ∈ a ∩ b. Because P is pairwise disjoint, two intersecting sets must be identical, so a = b. By card_le_one_iff, |C| ≤ 1.

    lines 24–71

    uses card_le_one_iff, card_sdiff_of_subset, card_pair, card_eq_one

      let C := P.filter (fun s => ¬ Disjoint s T)
      have hC_le_one : C.card ≤ 1 := by
        rw [card_le_one_iff]
        intro a b ha hb
        rw [mem_filter] at ha hb
        obtain ⟨haP, hadisj⟩ := ha
        obtain ⟨hbP, hbdisj⟩ := hb
        rw [disjoint_iff_inter_eq_empty] at hadisj hbdisj
        have ha_nonempty : (a ∩ T).Nonempty := nonempty_iff_ne_empty.mpr hadisj
        have hb_nonempty : (b ∩ T).Nonempty := nonempty_iff_ne_empty.mpr hbdisj
        obtain ⟨za, hza⟩ := ha_nonempty
        obtain ⟨zb, hzb⟩ := hb_nonempty
        rw [mem_inter] at hza hzb
        have hza_diff : za ∈ T \ {x, y} := by
          rw [mem_sdiff, mem_insert, mem_singleton, not_or]
          refine ⟨hza.2, ?_⟩
          constructor
          · rintro rfl; exact hPnotx a haP hza.1
          · rintro rfl; exact hPnoty a haP hza.1
        have hzb_diff : zb ∈ T \ {x, y} := by
          rw [mem_sdiff, mem_insert, mem_singleton, not_or]
          refine ⟨hzb.2, ?_⟩
          constructor
          · rintro rfl; exact hPnotx b hbP hzb.1
          · rintro rfl; exact hPnoty b hbP hzb.1
        have hsub : ({x, y} : Finset α) ⊆ T := by
          rw [insert_subset_iff, singleton_subset_iff]
          exact ⟨hxT, hyT⟩
        have hcard_diff : (T \ {x, y}).card = 1 := by
          rw [card_sdiff_of_subset hsub]
          have hxy_card : ({x, y} : Finset α).card = 2 := card_pair hyne.symm
          rw [hxy_card, hTcard]
        obtain ⟨z, hz⟩ := card_eq_one.mp hcard_diff
        have hza_z : za = z := by
          have := hza_diff
          rw [hz, mem_singleton] at this
          exact this
        have hzb_z : zb = z := by
          have := hzb_diff
          rw [hz, mem_singleton] at this
          exact this
        have h_eq : za = zb := hza_z.trans hzb_z.symm
        by_contra hab
        have hdisj : Disjoint a b := hPdisj haP hbP hab
        have h_inter : za ∈ a ∩ b := mem_inter.mpr ⟨hza.1, h_eq ▸ hzb.1⟩
        rw [disjoint_iff_inter_eq_empty] at hdisj
        rw [hdisj] at h_inter
        exact notMem_empty za h_inter
  4. The case |C| = 0 (no set in P intersects T) is impossible.

    If |C| = 0, then C = ∅, so every set in P is disjoint from T. Furthermore, T ∉ P because T is nonempty and thus intersects itself. Adding T to P yields a pairwise disjoint subcollection P ∪ {T} ⊆ F of size k + 1. This contradicts the hypothesis (hmax) that every packing in F has size at most k.

    lines 72–100

    uses Nat.le_one_iff_eq_zero_or_eq_one, card_eq_zero, card_insert_of_notMem, Set.pairwise_insert_of_symm, Nat.not_succ_le_self

      rcases Nat.le_one_iff_eq_zero_or_eq_one.mp hC_le_one with hC0 | hC1
      · have hCempty : C = ∅ := card_eq_zero.mp hC0
        have hTnotP : T ∉ P := by
          intro hTP
          have hCmem : T ∈ C := by
            rw [mem_filter]
            refine ⟨hTP, ?_⟩
            rw [disjoint_iff_inter_eq_empty, inter_self]
            intro hTempty
            rw [hTempty] at hTcard
            contradiction
          rw [hCempty] at hCmem
          exact notMem_empty T hCmem
        have hP'disj : ((insert T P : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by
          rw [coe_insert, Set.pairwise_insert_of_symm]
          refine ⟨hPdisj, ?_⟩
          intro b hb _
          have hbP : b ∈ P := hb
          have hbnotC : b ∉ C := by rw [hCempty]; exact notMem_empty b
          rw [mem_filter, not_and] at hbnotC
          have := hbnotC hbP
          have hdisj : Disjoint b T := not_not.mp this
          exact hdisj.symm
        have hP'sub : insert T P ⊆ F := insert_subset hTF hPF
        have hP'card : (insert T P).card = k + 1 := by
          rw [card_insert_of_notMem hTnotP, hPcard]
        have hle := hmax (insert T P) hP'sub hP'disj
        rw [hP'card] at hle
        exact Nat.not_succ_le_self k hle
  5. The case |C| = 1 (exactly one set in P intersects T) is also impossible, completing the contradiction.

    If |C| = 1, then C = {s0} for some s0 ∈ P. Replacing s0 with T gives the family P' = (P \\ {s0}) ∪ {T}. Since s0 was the unique set in P intersecting T, all remaining sets in P are disjoint from T, making P' pairwise disjoint. Because s0 ∈ P and T ∉ P \\ {s0}, the size of P' is (k - 1) + 1 = k. Thus P' is a maximum packing of size k in F containing T, contradicting the assumption (hnonextendable) that T belongs to no maximum packing.

    lines 101–140

    uses card_eq_one, Set.pairwise_insert_of_symm, card_insert_of_notMem, card_sdiff_of_subset, card_singleton, Nat.sub_add_cancel, mem_insert_self

      · obtain ⟨s0, hs0⟩ := card_eq_one.mp hC1
        have hs0C : s0 ∈ C := by rw [hs0, mem_singleton]
        rw [mem_filter] at hs0C
        have hs0P : s0 ∈ P := hs0C.1
        have hTnot : T ∉ P \ {s0} := by
          intro hTin
          rw [mem_sdiff, mem_singleton] at hTin
          have hTC : T ∈ C := by
            rw [mem_filter]
            refine ⟨hTin.1, ?_⟩
            rw [disjoint_iff_inter_eq_empty, inter_self]
            intro hTempty
            rw [hTempty] at hTcard
            contradiction
          rw [hs0, mem_singleton] at hTC
          exact hTin.2 hTC
        have hP'disj : ((insert T (P \ {s0}) : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by
          rw [coe_insert, Set.pairwise_insert_of_symm]
          refine ⟨hPdisj.mono (by rw [coe_sdiff, coe_singleton]; exact Set.sdiff_subset), ?_⟩
          intro b hb _
          rw [mem_coe, mem_sdiff, mem_singleton] at hb
          have hbP : b ∈ P := hb.1
          have hbne : b ≠ s0 := hb.2
          have hbnotC : b ∉ C := by rw [hs0, mem_singleton]; exact hbne
          rw [mem_filter, not_and] at hbnotC
          have := hbnotC hbP
          have hdisj : Disjoint b T := not_not.mp this
          exact hdisj.symm
        have hP'card : (insert T (P \ {s0})).card = k := by
          rw [card_insert_of_notMem hTnot]
          rw [card_sdiff_of_subset (singleton_subset_iff.mpr hs0P), card_singleton]
          rw [hPcard]
          have hk : 1 ≤ k := by
            have : 1 ≤ P.card := card_pos.mpr ⟨s0, hs0P⟩
            rwa [hPcard] at this
          exact Nat.sub_add_cancel hk
        have hP'sub : insert T (P \ {s0}) ⊆ F :=
          insert_subset hTF (sdiff_subset.trans hPF)
        have hTinP' : T ∈ insert T (P \ {s0}) := mem_insert_self T _
        exact hnonextendable (insert T (P \ {s0})) hP'sub hP'disj hP'card hTinP'
mem_biUnion
An element belongs to the union of a family of sets if and only if it belongs to at least one set in the family.
card_le_one_iff
A finite set has at most one element if and only if any two of its elements are equal.
card_sdiff_of_subset
If s is a subset of t, then the cardinality of t \\ s equals the cardinality of t minus the cardinality of s.
card_pair
The cardinality of a pair {a, b} is 2 whenever a ≠ b.
card_eq_one
A finite set has cardinality 1 if and only if it is a singleton set.
Nat.le_one_iff_eq_zero_or_eq_one
A natural number is at most 1 if and only if it is equal to 0 or equal to 1.
card_eq_zero
A finite set has cardinality 0 if and only if it is empty.
card_insert_of_notMem
Inserting an element not already in a finite set increases the set's cardinality by 1.
Set.pairwise_insert_of_symm
For a symmetric relation, inserting an element into a pairwise-related set yields a pairwise-related set if and only if the original set was pairwise-related and the new element is related to all elements in the set.
Nat.not_succ_le_self
No natural number has its successor less than or equal to itself (that is, ¬(n + 1 ≤ n)).
card_singleton
The cardinality of any singleton set {a} is 1.
Nat.sub_add_cancel
For natural numbers with m ≤ n, subtracting m and then adding m yields n.
mem_insert_self
An element is always a member of the set obtained by inserting it into any set.

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_three_set_stable_nonextendable_triple_patterns    {α : Type*} [DecidableEq α] (F : Finset (Finset α)) (k : ℕ)    (hthree : ∀ t ∈ F, t.card = 3)    (hmax : ∀ P : Finset (Finset α), P ⊆ F →      (P : Set (Finset α)).Pairwise Disjoint → P.card ≤ k)    (hstable : ∀ x ∈ F.biUnion id, ∃ P : Finset (Finset α),      P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧      ∀ s ∈ P, x ∉ s)    (T : Finset α) (hTF : T ∈ F)    (hnonextendable : ∀ P : Finset (Finset α), P ⊆ F →      (P : Set (Finset α)).Pairwise Disjoint → P.card = k → T ∉ P) :    ∀ x ∈ T, ∃ P : Finset (Finset α),      P ⊆ F ∧ (P : Set (Finset α)).Pairwise Disjoint ∧ P.card = k ∧      (∀ s ∈ P, x ∉ s) ∧      (∀ y ∈ T, y ≠ x → ∃ s ∈ P, y ∈ s) := by  open Finset in  intro x hxT  have hTcard : T.card = 3 := hthree T hTF  have hx_biUnion : x ∈ F.biUnion id := mem_biUnion.2 ⟨T, hTF, hxT⟩  obtain ⟨P, hPF, hPdisj, hPcard, hPnotx⟩ := hstable x hx_biUnion  refine ⟨P, hPF, hPdisj, hPcard, hPnotx, ?_⟩  by_contra! hmiss  obtain ⟨y, hyT, hyne, hPnoty⟩ := hmiss  let C := P.filter (fun s => ¬ Disjoint s T)  have hC_le_one : C.card ≤ 1 := by    rw [card_le_one_iff]    intro a b ha hb    rw [mem_filter] at ha hb    obtain ⟨haP, hadisj⟩ := ha    obtain ⟨hbP, hbdisj⟩ := hb    rw [disjoint_iff_inter_eq_empty] at hadisj hbdisj    have ha_nonempty : (a ∩ T).Nonempty := nonempty_iff_ne_empty.mpr hadisj    have hb_nonempty : (b ∩ T).Nonempty := nonempty_iff_ne_empty.mpr hbdisj    obtain ⟨za, hza⟩ := ha_nonempty    obtain ⟨zb, hzb⟩ := hb_nonempty    rw [mem_inter] at hza hzb    have hza_diff : za ∈ T \ {x, y} := by      rw [mem_sdiff, mem_insert, mem_singleton, not_or]      refine ⟨hza.2, ?_⟩      constructor      · rintro rfl; exact hPnotx a haP hza.1      · rintro rfl; exact hPnoty a haP hza.1    have hzb_diff : zb ∈ T \ {x, y} := by      rw [mem_sdiff, mem_insert, mem_singleton, not_or]      refine ⟨hzb.2, ?_⟩      constructor      · rintro rfl; exact hPnotx b hbP hzb.1      · rintro rfl; exact hPnoty b hbP hzb.1    have hsub : ({x, y} : Finset α) ⊆ T := by      rw [insert_subset_iff, singleton_subset_iff]      exact ⟨hxT, hyT⟩    have hcard_diff : (T \ {x, y}).card = 1 := by      rw [card_sdiff_of_subset hsub]      have hxy_card : ({x, y} : Finset α).card = 2 := card_pair hyne.symm      rw [hxy_card, hTcard]    obtain ⟨z, hz⟩ := card_eq_one.mp hcard_diff    have hza_z : za = z := by      have := hza_diff      rw [hz, mem_singleton] at this      exact this    have hzb_z : zb = z := by      have := hzb_diff      rw [hz, mem_singleton] at this      exact this    have h_eq : za = zb := hza_z.trans hzb_z.symm    by_contra hab    have hdisj : Disjoint a b := hPdisj haP hbP hab    have h_inter : za ∈ a ∩ b := mem_inter.mpr ⟨hza.1, h_eq ▸ hzb.1⟩    rw [disjoint_iff_inter_eq_empty] at hdisj    rw [hdisj] at h_inter    exact notMem_empty za h_inter  rcases Nat.le_one_iff_eq_zero_or_eq_one.mp hC_le_one with hC0 | hC1  · have hCempty : C = ∅ := card_eq_zero.mp hC0    have hTnotP : T ∉ P := by      intro hTP      have hCmem : T ∈ C := by        rw [mem_filter]        refine ⟨hTP, ?_⟩        rw [disjoint_iff_inter_eq_empty, inter_self]        intro hTempty        rw [hTempty] at hTcard        contradiction      rw [hCempty] at hCmem      exact notMem_empty T hCmem    have hP'disj : ((insert T P : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by      rw [coe_insert, Set.pairwise_insert_of_symm]      refine ⟨hPdisj, ?_⟩      intro b hb _      have hbP : b ∈ P := hb      have hbnotC : b ∉ C := by rw [hCempty]; exact notMem_empty b      rw [mem_filter, not_and] at hbnotC      have := hbnotC hbP      have hdisj : Disjoint b T := not_not.mp this      exact hdisj.symm    have hP'sub : insert T P ⊆ F := insert_subset hTF hPF    have hP'card : (insert T P).card = k + 1 := by      rw [card_insert_of_notMem hTnotP, hPcard]    have hle := hmax (insert T P) hP'sub hP'disj    rw [hP'card] at hle    exact Nat.not_succ_le_self k hle  · obtain ⟨s0, hs0⟩ := card_eq_one.mp hC1    have hs0C : s0 ∈ C := by rw [hs0, mem_singleton]    rw [mem_filter] at hs0C    have hs0P : s0 ∈ P := hs0C.1    have hTnot : T ∉ P \ {s0} := by      intro hTin      rw [mem_sdiff, mem_singleton] at hTin      have hTC : T ∈ C := by        rw [mem_filter]        refine ⟨hTin.1, ?_⟩        rw [disjoint_iff_inter_eq_empty, inter_self]        intro hTempty        rw [hTempty] at hTcard        contradiction      rw [hs0, mem_singleton] at hTC      exact hTin.2 hTC    have hP'disj : ((insert T (P \ {s0}) : Finset (Finset α)) : Set (Finset α)).Pairwise Disjoint := by      rw [coe_insert, Set.pairwise_insert_of_symm]      refine ⟨hPdisj.mono (by rw [coe_sdiff, coe_singleton]; exact Set.sdiff_subset), ?_⟩      intro b hb _      rw [mem_coe, mem_sdiff, mem_singleton] at hb      have hbP : b ∈ P := hb.1      have hbne : b ≠ s0 := hb.2      have hbnotC : b ∉ C := by rw [hs0, mem_singleton]; exact hbne      rw [mem_filter, not_and] at hbnotC      have := hbnotC hbP      have hdisj : Disjoint b T := not_not.mp this      exact hdisj.symm    have hP'card : (insert T (P \ {s0})).card = k := by      rw [card_insert_of_notMem hTnot]      rw [card_sdiff_of_subset (singleton_subset_iff.mpr hs0P), card_singleton]      rw [hPcard]      have hk : 1 ≤ k := by        have : 1 ≤ P.card := card_pos.mpr ⟨s0, hs0P⟩        rwa [hPcard] at this      exact Nat.sub_add_cancel hk    have hP'sub : insert T (P \ {s0}) ⊆ F :=      insert_subset hTF (sdiff_subset.trans hPF)    have hTinP' : T ∈ insert T (P \ {s0}) := mem_insert_self T _    exact hnonextendable (insert T (P \ {s0})) hP'sub hP'disj hP'card hTinP'
See it in the graphDiscuss this resultChallenge it