finite_maximum_packing_private_witnesses_intersect
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
- finite_maximum_packing_conflicts_satisfy_hallGiven a maximum packing P and any packing W of a finite set family, every subpacking X of W meets at least |X| members of P. Thus the…
- Used by 1
- simple_graph_maximum_packing_two_forced_edges_k4For a maximum triangle packing, if a packed triangle has two singleton-forced edges then its three vertices have a common fourth vertex…
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.
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.
uses
disjoint_self.mpclassical intro hTU have hne : T ≠ U := by intro h subst U exact (hnonempty T hT).ne_empty (disjoint_self.mp hTU)
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.
uses
Finset.mem_insert,Finset.mem_singletonlet 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
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.
uses
Finset.mem_coe,Finset.mem_insert,Finset.mem_singletonhave 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
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)}|.
uses
finite_maximum_packing_conflicts_satisfy_hall,Finset.Subset.rflhave hhall := finite_maximum_packing_conflicts_satisfy_hall F P W hnonempty hPF hWF hPdis hWdis hmax W (Finset.Subset.rfl)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.
uses
Finset.mem_filter.mp,Finset.disjoint_biUnion_right,Finset.mem_insert,Finset.mem_singletonhave 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
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.
uses
Finset.card_le_card,Finset.card_singletonhave 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
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_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