inter_eq_of_expandable_step
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₁$.
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.
uses
Finset.mem_interext x simp only [Finset.mem_inter] constructor
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₂$.
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 hmemUnder 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.
uses
Finset.mem_sdiff.mpr,Finset.disjoint_left.mphave 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⟩
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.
· 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
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.
/-- 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⟩