AFTD Auto-Formalizing Theoretical Domains

op_639_doubleton_fiber_outside_inter_pair

theoremverified

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

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.

  1. 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.

    lines 11–14

    uses Finset.disjoint_singleton_right, Finset.mem_sdiff.mp

      have hdisj1 : Disjoint (e ∩ T) (e1 ∩ T) := by
        rw [heS, he1x]
        rw [Finset.disjoint_singleton_right]
        exact (Finset.mem_sdiff.mp hx1).2
  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.

    lines 15–18

    uses Finset.disjoint_singleton_right, Finset.mem_sdiff.mp

      have hdisj2 : Disjoint (e ∩ T) (e2 ∩ T) := by
        rw [heS, he2x]
        rw [Finset.disjoint_singleton_right]
        exact (Finset.mem_sdiff.mp hx2).2
  3. 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.

    lines 19–20

    uses op_639_disjoint_trace_fibers_outside_inter

      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⟩
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

/-- 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⟩
See it in the graphDiscuss this resultChallenge it