AFTD Auto-Formalizing Theoretical Domains

distinct_of_inter_eq

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₂, 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₂.

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

    lines 3–4

      intro he
      subst he
  2. 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₂.

    lines 5–6

    uses Finset.inter_self

      have he1 : e₁ = X₁ ∩ X₂ := by
        rw [← hinter, Finset.inter_self]
  3. 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.

    lines 7–10

    uses Finset.Subset.antisymm, Finset.inter_subset_left

      have hX1 : X₁ = e₁ := by
        apply Finset.Subset.antisymm h1
        rw [he1]
        exact Finset.inter_subset_left
  4. 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.

    lines 11–14

    uses Finset.Subset.antisymm, Finset.inter_subset_right

      have hX2 : X₂ = e₁ := by
        apply Finset.Subset.antisymm h2
        rw [he1]
        exact Finset.inter_subset_right
  5. Contradiction: X₁ = X₂, contradicting X₁ ≠ X₂.

    Chaining X₁ = e₁ and e₁ = X₂ gives X₁ = X₂. This contradicts the hypothesis X₁ ≠ X₂ (hne).

    line 15

      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

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