op_639_doubleton_fiber_outside_inter_pair
Let F be intersecting, T a set, S a 2-element subset of T, and e in F with e ∩ T = S. If x1, x2 in T \ S have private singleton edges e1, e2 with e1 ∩ T = {x1} and e2 ∩ T = {x2}, then e \ T intersects both e1 \ T and e2 \ T.
Statement
theorem op_639_doubleton_fiber_outside_inter_pair {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (hinter : (F : Set (Finset V)).Intersecting) (T : Finset V) (S : Finset V) (e e1 e2 : Finset V) (he : e ∈ F) (he1 : e1 ∈ F) (he2 : e2 ∈ F) (heS : e ∩ T = S) (x1 x2 : V) (hx1 : x1 ∈ T \ S) (hx2 : x2 ∈ T \ S) (he1x : e1 ∩ T = {x1}) (he2x : e2 ∩ T = {x2}) : ¬Disjoint (e \ T) (e1 \ T) ∧ ¬Disjoint (e \ T) (e2 \ T)
- Source
- step towards op_639_intersecting_four_uniform_covering_four_card_le_forty_two
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- op_639_disjoint_trace_fibers_outside_interLet F be an intersecting family and T any set. If e1, e2 in F have disjoint intersections with T, then their differences e1 \ T and e2 \ T…
The proof, explained
To show that e \ T intersects both e1 \ T and e2 \ T outside T, the proof first establishes that the traces of e and each ei on T are disjoint. Since the trace of e is S and each ei has singleton trace {xi} with xi ∈ T \ S, neither xi belongs to S, which makes their traces on T disjoint. Because F is an intersecting family, any two edges with disjoint traces on T must intersect outside T, yielding the desired intersection for both pairs.
The traces of e and e1 on T are disjoint: Disjoint (e ∩ T) (e1 ∩ T).
Rewriting the traces using e ∩ T = S and e1 ∩ T = {x1} reduces the goal to Disjoint S {x1}. By Finset.disjoint_singleton_right, a set is disjoint from a singleton {x1} if and only if x1 ∉ S. Since x1 ∈ T \ S by hypothesis hx1, the second component of Finset.mem_sdiff.mp yields x1 ∉ S.
uses
Finset.disjoint_singleton_right,Finset.mem_sdiff.mphave hdisj1 : Disjoint (e ∩ T) (e1 ∩ T) := by rw [heS, he1x] rw [Finset.disjoint_singleton_right] exact (Finset.mem_sdiff.mp hx1).2
The traces of e and e2 on T are disjoint: Disjoint (e ∩ T) (e2 ∩ T).
Similarly, substituting e ∩ T = S and e2 ∩ T = {x2} reduces the disjointness to x2 ∉ S via Finset.disjoint_singleton_right. This follows directly from x2 ∈ T \ S via Finset.mem_sdiff.mp.
uses
Finset.disjoint_singleton_right,Finset.mem_sdiff.mphave hdisj2 : Disjoint (e ∩ T) (e2 ∩ T) := by rw [heS, he2x] rw [Finset.disjoint_singleton_right] exact (Finset.mem_sdiff.mp hx2).2
Neither e \ T and e1 \ T nor e \ T and e2 \ T are disjoint.
Because F is an intersecting family, any two edges whose traces on T are disjoint must intersect outside T by op_639_disjoint_trace_fibers_outside_inter. Applying this lemma to e and e1 (using hdisj1) shows ¬Disjoint (e \ T) (e1 \ T), and applying it to e and e2 (using hdisj2) shows ¬Disjoint (e \ T) (e2 \ T). Combining these two results establishes the conjunction.
uses
op_639_disjoint_trace_fibers_outside_interexact ⟨op_639_disjoint_trace_fibers_outside_inter F hinter T e e1 he he1 hdisj1, op_639_disjoint_trace_fibers_outside_inter F hinter T e e2 he he2 hdisj2⟩
Finset.disjoint_singleton_right- A finite set is disjoint from a singleton {a} if and only if a is not an element of the set.
Finset.mem_sdiff.mp- If an element belongs to the difference of two sets s \\ t, then it belongs to s and does not belong to t.
op_639_disjoint_trace_fibers_outside_inter- In an intersecting family, if two edges have disjoint traces on a set T, then their differences with T are not disjoint (they intersect outside T).
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.
/-- For any 2-element trace S in T and any private singleton edges e1, e2 for elements of T \ S, every edge in the fiber of S intersects both e1 \ T and e2 \ T outside T. -/theorem op_639_doubleton_fiber_outside_inter_pair {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (hinter : (F : Set (Finset V)).Intersecting) (T : Finset V) (S : Finset V) (e e1 e2 : Finset V) (he : e ∈ F) (he1 : e1 ∈ F) (he2 : e2 ∈ F) (heS : e ∩ T = S) (x1 x2 : V) (hx1 : x1 ∈ T \ S) (hx2 : x2 ∈ T \ S) (he1x : e1 ∩ T = {x1}) (he2x : e2 ∩ T = {x2}) : ¬Disjoint (e \ T) (e1 \ T) ∧ ¬Disjoint (e \ T) (e2 \ T) := by have hdisj1 : Disjoint (e ∩ T) (e1 ∩ T) := by rw [heS, he1x] rw [Finset.disjoint_singleton_right] exact (Finset.mem_sdiff.mp hx1).2 have hdisj2 : Disjoint (e ∩ T) (e2 ∩ T) := by rw [heS, he2x] rw [Finset.disjoint_singleton_right] exact (Finset.mem_sdiff.mp hx2).2 exact ⟨op_639_disjoint_trace_fibers_outside_inter F hinter T e e1 he he1 hdisj1, op_639_disjoint_trace_fibers_outside_inter F hinter T e e2 he he2 hdisj2⟩