distinct_of_inter_eq
Let V be a type with decidable equality, and let X₁, X₂, e₁, e₂ be finite sets (Finset V). If X₁ ⊆ e₁, X₂ ⊆ e₂, e₁ ∩ e₂ = X₁ ∩ X₂, and X₁ ≠ X₂, then e₁ ≠ e₂.
Statement
theorem distinct_of_inter_eq {V : Type*} [DecidableEq V] {X₁ X₂ e₁ e₂ : Finset V} (h1 : X₁ ⊆ e₁) (h2 : X₂ ⊆ e₂) (hinter : e₁ ∩ e₂ = X₁ ∩ X₂) (hne : X₁ ≠ X₂) : e₁ ≠ e₂
- 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₁ ∩ e₂ = X₁ ∩ X₂, and X₁ ≠ X₂, then e₁ ≠ e₂.
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 proof proceeds by contradiction: suppose e₁ = e₂. Then the intersection identity simplifies to e₁ = e₁ ∩ e₁ = X₁ ∩ X₂. Since X₁ and X₂ are both sandwiched between this intersection and e₁, antisymmetry forces X₁ = e₁ and X₂ = e₁, implying X₁ = X₂ and contradicting X₁ ≠ X₂.
It suffices to derive a contradiction assuming e₁ = e₂.
We argue by contradiction: assume e₁ = e₂ (he). Substituting e₁ for e₂ throughout the hypotheses leaves us to deduce False.
intro he subst he
e₁ = X₁ ∩ X₂
Under the assumption e₁ = e₂, the hypothesis e₁ ∩ e₂ = X₁ ∩ X₂ (hinter) becomes e₁ ∩ e₁ = X₁ ∩ X₂. Since the intersection of a set with itself is itself (Finset.inter_self), this gives e₁ = X₁ ∩ X₂.
uses
Finset.inter_selfhave he1 : e₁ = X₁ ∩ X₂ := by rw [← hinter, Finset.inter_self]
X₁ = e₁
By antisymmetry of set inclusion (Finset.Subset.antisymm), it suffices to show mutual inclusion. The inclusion X₁ ⊆ e₁ is given directly by assumption (h1). For the reverse inclusion, substituting e₁ = X₁ ∩ X₂ yields X₁ ∩ X₂ ⊆ X₁, which holds by Finset.inter_subset_left.
uses
Finset.Subset.antisymm,Finset.inter_subset_lefthave hX1 : X₁ = e₁ := by apply Finset.Subset.antisymm h1 rw [he1] exact Finset.inter_subset_left
X₂ = e₁
Similarly, mutual inclusion via Finset.Subset.antisymm proves X₂ = e₁. The inclusion X₂ ⊆ e₁ is given by assumption (h2, since e₂ = e₁). For the other direction, substituting e₁ = X₁ ∩ X₂ yields X₁ ∩ X₂ ⊆ X₂, which holds by Finset.inter_subset_right.
uses
Finset.Subset.antisymm,Finset.inter_subset_righthave hX2 : X₂ = e₁ := by apply Finset.Subset.antisymm h2 rw [he1] exact Finset.inter_subset_right
Contradiction: X₁ = X₂, contradicting X₁ ≠ X₂.
Chaining X₁ = e₁ and e₁ = X₂ gives X₁ = X₂. This contradicts the hypothesis X₁ ≠ X₂ (hne).
exact hne (hX1.trans hX2.symm)
Finset.inter_self- The intersection of a finite set with itself is the set itself: s ∩ s = s.
Finset.Subset.antisymm- If two finite sets are subsets of each other, they are equal: s₁ ⊆ s₂ and s₂ ⊆ s₁ imply s₁ = s₂.
Finset.inter_subset_left- The intersection of two finite sets is a subset of the first: s₁ ∩ s₂ ⊆ s₁.
Finset.inter_subset_right- The intersection of two finite sets is a subset of the second: s₁ ∩ s₂ ⊆ s₂.
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.
/-- If e₁ = e₂, then e₁ = e₁ ∩ e₂ = X₁ ∩ X₂, forcing X₁ = e₁ = X₂, contradicting X₁ ≠ X₂. -/theorem distinct_of_inter_eq {V : Type*} [DecidableEq V] {X₁ X₂ e₁ e₂ : Finset V} (h1 : X₁ ⊆ e₁) (h2 : X₂ ⊆ e₂) (hinter : e₁ ∩ e₂ = X₁ ∩ X₂) (hne : X₁ ≠ X₂) : e₁ ≠ e₂ := by intro he subst he have he1 : e₁ = X₁ ∩ X₂ := by rw [← hinter, Finset.inter_self] have hX1 : X₁ = e₁ := by apply Finset.Subset.antisymm h1 rw [he1] exact Finset.inter_subset_left have hX2 : X₂ = e₁ := by apply Finset.Subset.antisymm h2 rw [he1] exact Finset.inter_subset_right exact hne (hX1.trans hX2.symm)