AFTD Auto-Formalizing Theoretical Domains

finite_maximum_packing_private_witnesses_intersect

theoremverified

In a finite set family with nonempty members, if P is a maximum pairwise-disjoint packing and two family members each avoid every member of P except possibly p, then the two family members intersect.

Statement

theorem finite_maximum_packing_private_witnesses_intersect
    {α : Type*} [DecidableEq α] (F P : Finset (Finset α))
    (hnonempty : ∀ t ∈ F, t.Nonempty)
    (hPF : P ⊆ F)
    (hPdis : (P : Set (Finset α)).Pairwise Disjoint)
    (hmax : ∀ Q : Finset (Finset α), Q ⊆ F →
      (Q : Set (Finset α)).Pairwise Disjoint → Q.card ≤ P.card)
    (p T U : Finset α) (hT : T ∈ F) (hU : U ∈ F)
    (hTprivate : ∀ q ∈ P, q ≠ p → Disjoint q T)
    (hUprivate : ∀ q ∈ P, q ≠ p → Disjoint q U) :
    ¬ Disjoint T U
Source
Elementary maximum-packing exchange for the active-vertex reduction.
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The proof proceeds by contradiction: suppose T and U are disjoint. Because members of F are nonempty, T and U must be distinct, so W = {T, U} is a pairwise-disjoint subfamily of F of size 2. By Hall's condition for maximum packings (finite_maximum_packing_conflicts_satisfy_hall), at least |W| = 2 elements of P must intersect ⋃ W. However, every element of P except possibly p avoids both T and U, so at most one element of P (namely p) can intersect ⋃ W, yielding the contradiction 2 ≤ 1.

  1. Under the contradiction assumption that T and U are disjoint, T and U must be distinct (T ≠ U).

    We assume for contradiction that T and U are disjoint. If they were equal, T would be disjoint from itself, implying T = ∅ by disjoint_self.mp. Since all members of F are nonempty, this is a contradiction, so T ≠ U.

    lines 12–17

    uses disjoint_self.mp

      classical
      intro hTU
      have hne : T ≠ U := by
        intro h
        subst U
        exact (hnonempty T hT).ne_empty (disjoint_self.mp hTU)
  2. The two-element family W = {T, U} is a subfamily of F.

    We define W = {T, U}. Any element of W is either T or U (by Finset.mem_insert and Finset.mem_singleton), both of which are given to be in F.

    lines 18–24

    uses Finset.mem_insert, Finset.mem_singleton

      let W : Finset (Finset α) := {T,U}
      have hWF : W ⊆ F := by
        intro q hq
        simp only [W, Finset.mem_insert, Finset.mem_singleton] at hq
        rcases hq with rfl | rfl
        · exact hT
        · exact hU
  3. The members of W = {T, U} are pairwise disjoint.

    Any two distinct elements of W must be T and U in some order (using Finset.mem_coe, Finset.mem_insert, and Finset.mem_singleton). They are disjoint by the contradiction assumption that T and U are disjoint.

    lines 25–32

    uses Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton

      have hWdis : (W : Set (Finset α)).Pairwise Disjoint := by
        intro a ha b hb hab
        simp only [W, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at ha hb
        rcases ha with rfl | rfl <;> rcases hb with rfl | rfl
        · exact (hab rfl).elim
        · exact hTU
        · exact hTU.symm
        · exact (hab rfl).elim
  4. The number of sets in P intersecting ⋃ W is at least |W|.

    Because P is a maximum pairwise-disjoint packing and W ⊆ F is pairwise disjoint, Hall's condition for maximum packings (finite_maximum_packing_conflicts_satisfy_hall) applied to X = W (using Finset.Subset.rfl) implies |W| ≤ |{q ∈ P | ¬ Disjoint q (⋃ W)}|.

    lines 33–34

    uses finite_maximum_packing_conflicts_satisfy_hall, Finset.Subset.rfl

      have hhall := finite_maximum_packing_conflicts_satisfy_hall F P W
        hnonempty hPF hWF hPdis hWdis hmax W (Finset.Subset.rfl)
  5. The only set in P that can intersect ⋃ W is p, so {q ∈ P | ¬ Disjoint q (⋃ W)} ⊆ {p}.

    Suppose some q ∈ P intersects ⋃ W = T ∪ U and q ≠ p. By the privacy hypotheses, q is disjoint from T and from U. By Finset.disjoint_biUnion_right, q is disjoint from their union ⋃ W, which contradicts the membership condition in the filtered set (extracted via Finset.mem_filter.mp). Hence any such q must equal p.

    lines 35–49

    uses Finset.mem_filter.mp, Finset.disjoint_biUnion_right, Finset.mem_insert, Finset.mem_singleton

      have hsub : P.filter (fun q => ¬ Disjoint q (W.biUnion id)) ⊆ {p} := by
        intro q hq
        by_contra hn
        have hqp : q ≠ p := by simpa using hn
        have hqP : q ∈ P := (Finset.mem_filter.mp hq).1
        have hdT := hTprivate q hqP hqp
        have hdU := hUprivate q hqP hqp
        have hd : Disjoint q (W.biUnion id) := by
          rw [Finset.disjoint_biUnion_right]
          intro s hs
          simp only [W, Finset.mem_insert, Finset.mem_singleton] at hs
          rcases hs with rfl | rfl
          · exact hdT
          · exact hdU
        exact (Finset.mem_filter.mp hq).2 hd
  6. The cardinality bounds |W| = 2 and |{q ∈ P | ¬ Disjoint q (⋃ W)}| ≤ 1 yield a contradiction (2 ≤ 1).

    Because T ≠ U, |W| = 2. On the other hand, the inclusion into {p} implies |{q ∈ P | ¬ Disjoint q (⋃ W)}| ≤ |{p}| = 1 by Finset.card_le_card and Finset.card_singleton. Substituting these into Hall's inequality yields 2 ≤ 1, an arithmetic contradiction closed by omega.

    lines 50–54

    uses Finset.card_le_card, Finset.card_singleton

      have hcard := Finset.card_le_card hsub
      have hWcard : W.card = 2 := by simp [W, hne]
      rw [hWcard] at hhall
      simp only [Finset.card_singleton] at hcard
      omega
disjoint_self.mp
A set that is disjoint from itself is empty.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton set {a} if and only if it equals a.
Finset.mem_coe
An element belongs to the set coercion of a finset if and only if it belongs to the finset.
finite_maximum_packing_conflicts_satisfy_hall
In a family of nonempty sets, any pairwise disjoint subfamily W satisfies Hall's condition with respect to a maximum packing P: for any X ⊆ W, |X| is at most the number of members of P intersecting ⋃ X.
Finset.Subset.rfl
Every finset is a subset of itself.
Finset.mem_filter.mp
An element of a filtered finset belongs to the underlying finset and satisfies the filtering predicate.
Finset.disjoint_biUnion_right
A set is disjoint from a union of sets if and only if it is disjoint from each set in the collection.
Finset.card_le_card
If one finset is a subset of another, its cardinality is less than or equal to that of the other.
Finset.card_singleton
A singleton finset {a} has cardinality 1.

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_maximum_packing_private_witnesses_intersect    {α : Type*} [DecidableEq α] (F P : Finset (Finset α))    (hnonempty : ∀ t ∈ F, t.Nonempty)    (hPF : P ⊆ F)    (hPdis : (P : Set (Finset α)).Pairwise Disjoint)    (hmax : ∀ Q : Finset (Finset α), Q ⊆ F →      (Q : Set (Finset α)).Pairwise Disjoint → Q.card ≤ P.card)    (p T U : Finset α) (hT : T ∈ F) (hU : U ∈ F)    (hTprivate : ∀ q ∈ P, q ≠ p → Disjoint q T)    (hUprivate : ∀ q ∈ P, q ≠ p → Disjoint q U) :    ¬ Disjoint T U := by  classical  intro hTU  have hne : T ≠ U := by    intro h    subst U    exact (hnonempty T hT).ne_empty (disjoint_self.mp hTU)  let W : Finset (Finset α) := {T,U}  have hWF : W ⊆ F := by    intro q hq    simp only [W, Finset.mem_insert, Finset.mem_singleton] at hq    rcases hq with rfl | rfl    · exact hT    · exact hU  have hWdis : (W : Set (Finset α)).Pairwise Disjoint := by    intro a ha b hb hab    simp only [W, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at ha hb    rcases ha with rfl | rfl <;> rcases hb with rfl | rfl    · exact (hab rfl).elim    · exact hTU    · exact hTU.symm    · exact (hab rfl).elim  have hhall := finite_maximum_packing_conflicts_satisfy_hall F P W    hnonempty hPF hWF hPdis hWdis hmax W (Finset.Subset.rfl)  have hsub : P.filter (fun q => ¬ Disjoint q (W.biUnion id)) ⊆ {p} := by    intro q hq    by_contra hn    have hqp : q ≠ p := by simpa using hn    have hqP : q ∈ P := (Finset.mem_filter.mp hq).1    have hdT := hTprivate q hqP hqp    have hdU := hUprivate q hqP hqp    have hd : Disjoint q (W.biUnion id) := by      rw [Finset.disjoint_biUnion_right]      intro s hs      simp only [W, Finset.mem_insert, Finset.mem_singleton] at hs      rcases hs with rfl | rfl      · exact hdT      · exact hdU    exact (Finset.mem_filter.mp hq).2 hd  have hcard := Finset.card_le_card hsub  have hWcard : W.card = 2 := by simp [W, hne]  rw [hWcard] at hhall  simp only [Finset.card_singleton] at hcard  omega
See it in the graphDiscuss this resultChallenge it