AFTD Auto-Formalizing Theoretical Domains

codeword_ne_of_supp_inter_singleton

theoremverified

Let $\alpha$ be an alphabet with decidable equality and zero element $0$. If $x, y : \mathrm{Fin}\, n \to \alpha$ are codewords such that $x$ has support cardinality $(\mathrm{codeword\_supp}(x)).\mathrm{card} = 2$ and the intersection of their supports is a singleton $\mathrm{codeword\_supp}(x) \cap \mathrm{codeword\_supp}(y) = \{i\}$, then $x \ne y$.

Statement

theorem codeword_ne_of_supp_inter_singleton
    {n : ℕ} {α : Type*} [DecidableEq α] [Zero α]
    (x y : Fin n → α) (i : Fin n)
    (hx_wt : (codeword_supp x).card = 2)
    (h_inter : codeword_supp x ∩ codeword_supp y = {i}) :
    x ≠ y
Source
arXiv:2610.30613, Lemma 2.1
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • codeword_suppThe support of a codeword $x : \mathrm{Fin}\, n \to \alpha$ over an alphabet $\alpha$ with decidable equality and zero is the finite set…
Used by 1

Read back from the Lean

For any natural number $n$, any type $\alpha$ with decidable equality and a zero element, any two vectors $x, y : \mathrm{Fin}\ n \to \alpha$, and any index $i : \mathrm{Fin}\ n$, if the support of $x$ (codeword_supp x) has cardinality 2 and the intersection of the support of $x$ and the support of $y$ is the singleton set $\{i\}$, then $x \neq y$.

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: assuming x = y, the intersection of their supports simplifies to codeword_supp(x) ∩ codeword_supp(x) = codeword_supp(x). By hypothesis, this intersection is the singleton {i}, which implies codeword_supp(x) = {i}. This contradicts the assumption that the support of x has cardinality 2, since a singleton has cardinality 1.

  1. It suffices to derive a contradiction under the assumption that x = y.

    We assume for contradiction that the two codewords are equal (x = y) and substitute x for y throughout the hypotheses, simplifying the intersection equation to codeword_supp(x) ∩ codeword_supp(x) = {i}.

    lines 8–9

      intro hxy
      subst hxy
  2. The support of x is the singleton {i}.

    Because the intersection of any set with itself is the set itself (Finset.inter_self), the hypothesis codeword_supp(x) ∩ codeword_supp(x) = {i} simplifies directly to codeword_supp(x) = {i}.

    line 10

    uses Finset.inter_self

      simp only [Finset.inter_self] at h_inter
  3. The weight hypothesis leads to a contradiction.

    Substituting codeword_supp(x) = {i} into the weight assumption |codeword_supp(x)| = 2 yields |{i}| = 2. Since the cardinality of a singleton is 1, simplifying this equation produces 1 = 2, which is false and completes the proof by contradiction.

    lines 11–12

      rw [h_inter] at hx_wt
      simp at hx_wt
Finset.inter_self
For any finite set s, its intersection with itself is s (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

/-- Two codewords are distinct if one has weight 2 and their supports intersect in a single coordinate. -/theorem codeword_ne_of_supp_inter_singleton    {n : ℕ} {α : Type*} [DecidableEq α] [Zero α]    (x y : Fin n → α) (i : Fin n)    (hx_wt : (codeword_supp x).card = 2)    (h_inter : codeword_supp x ∩ codeword_supp y = {i}) :    x ≠ y := by  intro hxy  subst hxy  simp only [Finset.inter_self] at h_inter  rw [h_inter] at hx_wt  simp at hx_wt
See it in the graphDiscuss this resultChallenge it