AFTD Auto-Formalizing Theoretical Domains

op_639_disjoint_trace_fibers_outside_inter

theoremverified

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

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.

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

    lines 9–11

    uses Finset.not_disjoint_iff

      have hne : ¬Disjoint e1 e2 := hinter he1 he2
      rw [Finset.not_disjoint_iff] at hne ⊢
      rcases hne with ⟨x, hx1, hx2⟩
  2. 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.

    lines 12–16

    uses Finset.mem_inter.mpr, Finset.disjoint_left.mp

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

    line 17

    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

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