AFTD Auto-Formalizing Theoretical Domains

inter_eq_of_expandable_step

theoremverified

Let V be a type with decidable equality, and let X₁, X₂, e₁, e₂ be finite sets (Finset V). If X₁ ⊆ e₁, X₂ ⊆ e₂, Disjoint e₁ (X₂ \ X₁), and Disjoint e₂ (e₁ \ X₂), then e₁ ∩ e₂ = X₁ ∩ X₂.

Statement

theorem inter_eq_of_expandable_step {V : Type*} [DecidableEq V] {X₁ X₂ e₁ e₂ : Finset V} (h1 : X₁ ⊆ e₁) (h2 : X₂ ⊆ e₂) (hd1 : Disjoint e₁ (X₂ \ X₁)) (hd2 : Disjoint e₂ (e₁ \ X₂)) : e₁ ∩ e₂ = X₁ ∩ X₂
Source
arXiv:2611.16957, Lemma 3.3 proof
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For any type $V$ with decidable equality, and for any finite subsets $X₁, X₂, e₁, e₂$ of $V$, if $X₁ ⊆ e₁$, $X₂ ⊆ e₂$, $e₁$ is disjoint from $X₂ \setminus X₁$, and $e₂$ is disjoint from $e₁ \setminus X₂$, then $e₁ ∩ e₂ = X₁ ∩ X₂$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The equality $e₁ ∩ e₂ = X₁ ∩ X₂$ is proved by showing double inclusion for an arbitrary element $x$. The reverse inclusion $X₁ ∩ X₂ ⊆ e₁ ∩ e₂$ is immediate from the assumptions $X₁ ⊆ e₁$ and $X₂ ⊆ e₂$. For the forward inclusion, assuming $x ∈ e₁ ∩ e₂$, the disjointness of $e₂$ and $e₁ \setminus X₂$ forces $x ∈ X₂$, after which the disjointness of $e₁$ and $X₂ \setminus X₁$ forces $x ∈ X₁$.

  1. To prove $e₁ ∩ e₂ = X₁ ∩ X₂$, it suffices to show that for an arbitrary element $x$, $x ∈ e₁ ∧ x ∈ e₂ ↔ x ∈ X₁ ∧ x ∈ X₂$.

    By set extensionality (`ext x`), two finite sets are equal if they contain the same elements. Rewriting intersection membership using `Finset.mem_inter` turns membership in the intersections into conjunctions of memberships. Splitting the biconditional (`constructor`) leaves two implications to verify.

    lines 3–5

    uses Finset.mem_inter

      ext x
      simp only [Finset.mem_inter]
      constructor
  2. If $x ∈ e₁$ and $x ∈ e₂$, then $x ∈ X₂$.

    Assume $x ∈ e₁$ and $x ∈ e₂$. To show $x ∈ X₂$, we argue by contradiction: suppose $x ∉ X₂$. Then $x ∈ e₁ \setminus X₂$ by `Finset.mem_sdiff.mpr`. However, the hypothesis `hd2` states that $e₂$ and $e₁ \setminus X₂$ are disjoint. Applying `Finset.disjoint_left.mp` to `hd2` and $x ∈ e₂$ gives $x ∉ e₁ \setminus X₂$, which contradicts $x ∈ e₁ \setminus X₂$.

    lines 6–10

    uses Finset.mem_sdiff.mpr, Finset.disjoint_left.mp

      · rintro ⟨he1, he2⟩
        have hx2 : x ∈ X₂ := by
          by_contra hnot
          have hmem : x ∈ e₁ \ X₂ := Finset.mem_sdiff.mpr ⟨he1, hnot⟩
          exact Finset.disjoint_left.mp hd2 he2 hmem
  3. Under the same assumptions, $x ∈ X₁$, completing the forward implication $x ∈ X₁ ∧ x ∈ X₂$.

    To show $x ∈ X₁$, we argue by contradiction again: suppose $x ∉ X₁$. Since we already proved $x ∈ X₂$, we obtain $x ∈ X₂ \setminus X₁$ via `Finset.mem_sdiff.mpr`. But hypothesis `hd1` states that $e₁$ and $X₂ \setminus X₁$ are disjoint. By `Finset.disjoint_left.mp`, since $x ∈ e₁$, we have $x ∉ X₂ \setminus X₁$, a contradiction. Combining $x ∈ X₁$ and $x ∈ X₂$ yields the forward direction.

    lines 11–15

    uses Finset.mem_sdiff.mpr, Finset.disjoint_left.mp

        have hx1 : x ∈ X₁ := by
          by_contra hnot
          have hmem : x ∈ X₂ \ X₁ := Finset.mem_sdiff.mpr ⟨hx2, hnot⟩
          exact Finset.disjoint_left.mp hd1 he1 hmem
        exact ⟨hx1, hx2⟩
  4. If $x ∈ X₁$ and $x ∈ X₂$, then $x ∈ e₁$ and $x ∈ e₂$.

    Assume $x ∈ X₁$ and $x ∈ X₂$. Since $X₁ ⊆ e₁$ by hypothesis `h1`, we have $x ∈ e₁$. Similarly, since $X₂ ⊆ e₂$ by hypothesis `h2`, we have $x ∈ e₂$. This establishes the reverse implication.

    lines 16–17

      · rintro ⟨hx1, hx2⟩
        exact ⟨h1 hx1, h2 hx2⟩
Finset.mem_inter
An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
Finset.disjoint_left.mp
If two finite sets are disjoint, an element belonging to the first cannot belong to the second.
Finset.mem_sdiff.mpr
If an element belongs to a finite set and does not belong to another, it belongs to their set difference.

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

/-- Two edges e₁, e₂ containing X₁, X₂ respectively have intersection X₁ ∩ X₂ if each avoids the remainder of the other set. -/theorem inter_eq_of_expandable_step {V : Type*} [DecidableEq V] {X₁ X₂ e₁ e₂ : Finset V} (h1 : X₁ ⊆ e₁) (h2 : X₂ ⊆ e₂) (hd1 : Disjoint e₁ (X₂ \ X₁)) (hd2 : Disjoint e₂ (e₁ \ X₂)) : e₁ ∩ e₂ = X₁ ∩ X₂ := by  ext x  simp only [Finset.mem_inter]  constructor  · rintro ⟨he1, he2⟩    have hx2 : x ∈ X₂ := by      by_contra hnot      have hmem : x ∈ e₁ \ X₂ := Finset.mem_sdiff.mpr ⟨he1, hnot⟩      exact Finset.disjoint_left.mp hd2 he2 hmem    have hx1 : x ∈ X₁ := by      by_contra hnot      have hmem : x ∈ X₂ \ X₁ := Finset.mem_sdiff.mpr ⟨hx2, hnot⟩      exact Finset.disjoint_left.mp hd1 he1 hmem    exact ⟨hx1, hx2⟩  · rintro ⟨hx1, hx2⟩    exact ⟨h1 hx1, h2 hx2⟩
See it in the graphDiscuss this resultChallenge it