op_639_disjoint_trace_fibers_outside_inter
Let 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 must not be disjoint.
Statement
theorem op_639_disjoint_trace_fibers_outside_inter {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (hinter : (F : Set (Finset V)).Intersecting) (T : Finset V) (e1 e2 : Finset V) (he1 : e1 ∈ F) (he2 : e2 ∈ F) (hdisj : Disjoint (e1 ∩ T) (e2 ∩ T)) : ¬Disjoint (e1 \ 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- Used by 1
- op_639_doubleton_fiber_outside_inter_pairLet 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,…
The proof, explained
Because F is an intersecting family, the edges e1 and e2 must share at least one vertex x. If x were in T, it would belong to both e1 ∩ T and e2 ∩ T, contradicting the assumption that these traces are disjoint. Hence x cannot belong to T, which places x in both e1 \\ T and e2 \\ T and shows that these differences are not disjoint.
There is an element x belonging to both e1 and e2, and it suffices to show that e1 \\ T and e2 \\ T share an element.
Since F is an intersecting family, the edges e1 and e2 cannot be disjoint. Rewriting non-disjointness via Finset.not_disjoint_iff both in this fact and in the goal reduces the problem to finding an element in (e1 \\ T) ∩ (e2 \\ T), and provides a common vertex x ∈ e1 ∩ e2.
uses
Finset.not_disjoint_iffhave hne : ¬Disjoint e1 e2 := hinter he1 he2 rw [Finset.not_disjoint_iff] at hne ⊢ rcases hne with ⟨x, hx1, hx2⟩
The common element x cannot belong to T.
We consider whether x ∈ T. If it were, x would belong to both e1 ∩ T and e2 ∩ T. But this contradicts the hypothesis hdisj that e1 ∩ T and e2 ∩ T are disjoint.
uses
Finset.mem_inter.mpr,Finset.disjoint_left.mpby_cases hxT : x ∈ T · exfalso have h1 : x ∈ e1 ∩ T := Finset.mem_inter.mpr ⟨hx1, hxT⟩ have h2 : x ∈ e2 ∩ T := Finset.mem_inter.mpr ⟨hx2, hxT⟩ exact Finset.disjoint_left.mp hdisj h1 h2
x belongs to both e1 \\ T and e2 \\ T, proving that the two sets are not disjoint.
In the remaining case x ∉ T, the vertex x belongs to e1 \\ T and to e2 \\ T by the definition of set difference, thereby witnessing that (e1 \\ T) and (e2 \\ T) are not disjoint.
uses
Finset.mem_sdiff.mpr· refine ⟨x, Finset.mem_sdiff.mpr ⟨hx1, hxT⟩, Finset.mem_sdiff.mpr ⟨hx2, hxT⟩⟩
Finset.not_disjoint_iff- Two finite sets are not disjoint if and only if they share a common element.
Finset.mem_inter.mpr- An element belongs to the intersection of two finite sets if it belongs to both sets.
Finset.disjoint_left.mp- If two finite sets are disjoint, an element belonging to the first set cannot belong to the second set.
Finset.mem_sdiff.mpr- An element belongs to the set difference s \\ t if it belongs to s and does not belong to 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 two edges in an intersecting hypergraph having disjoint traces on T, their outside traces e1 \ T and e2 \ T must intersect. -/theorem op_639_disjoint_trace_fibers_outside_inter {V : Type*} [DecidableEq V] (F : Finset (Finset V)) (hinter : (F : Set (Finset V)).Intersecting) (T : Finset V) (e1 e2 : Finset V) (he1 : e1 ∈ F) (he2 : e2 ∈ F) (hdisj : Disjoint (e1 ∩ T) (e2 ∩ T)) : ¬Disjoint (e1 \ T) (e2 \ T) := by have hne : ¬Disjoint e1 e2 := hinter he1 he2 rw [Finset.not_disjoint_iff] at hne ⊢ rcases hne with ⟨x, hx1, hx2⟩ by_cases hxT : x ∈ T · exfalso have h1 : x ∈ e1 ∩ T := Finset.mem_inter.mpr ⟨hx1, hxT⟩ have h2 : x ∈ e2 ∩ T := Finset.mem_inter.mpr ⟨hx2, hxT⟩ exact Finset.disjoint_left.mp hdisj h1 h2 · refine ⟨x, Finset.mem_sdiff.mpr ⟨hx1, hxT⟩, Finset.mem_sdiff.mpr ⟨hx2, hxT⟩⟩