codeword_ne_of_supp_inter_singleton
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
- two_four_code_sync_single_coordLet $\alpha$ be an alphabet with decidable equality and a distinguished element $0$. Let…
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.
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}.
intro hxy subst hxy
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}.
uses
Finset.inter_selfsimp only [Finset.inter_self] at h_inter
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.
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
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 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