codeword_supp_diff_card_le_hammingDist
For any two codewords $x, y : \mathrm{Fin}\, n \to \alpha$, the sum of the cardinalities of the set differences of their supports, $(\mathrm{codeword\_supp}(x) \setminus \mathrm{codeword\_supp}(y)).\mathrm{card} + (\mathrm{codeword\_supp}(y) \setminus \mathrm{codeword\_supp}(x)).\mathrm{card}$, is at most their Hamming distance $\mathrm{hammingDist}(x, y)$.
Statement
theorem codeword_supp_diff_card_le_hammingDist {n : ℕ} {α : Type*} [DecidableEq α] [Zero α] (x y : Fin n → α) : (codeword_supp x \ codeword_supp y).card + (codeword_supp y \ codeword_supp x).card ≤ hammingDist x y
- Source
- arXiv:2610.30613, Proof of Lemma 3.3
- Verified
- 25 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_four_supports_intersect_ge_twoLet $\alpha$ be an alphabet with decidable equality and a distinguished element $0$. Let…
Read back from the Lean
For every natural number $n$, every type $\alpha$ equipped with decidable equality and a zero element, and all functions $x, y : \mathrm{Fin}(n) \to \alpha$, the cardinality of the difference of the support of $x$ and the support of $y$ plus the cardinality of the difference of the support of $y$ and the support of $x$ (i.e., the size of the symmetric difference of their supports) is less than or equal to the Hamming distance between $x$ and $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 shows that the sum of the cardinalities of the two set differences equals the cardinality of their union, since differences A \ B and B \ A are always disjoint. Because the Hamming distance is by definition the number of coordinates where the two codewords differ, the cardinality inequality reduces to showing that this union is a subset of the difference set {i | x i ≠ y i}. For any coordinate in the union, one codeword is nonzero while the other is zero, which immediately implies that the two codewords cannot be equal at that coordinate.
The sum of the sizes of the two set differences equals the cardinality of their union.
Because the set differences (codeword_supp x \ codeword_supp y) and (codeword_supp y \ codeword_supp x) are always disjoint (by disjoint_sdiff_sdiff), the sum of their cardinalities equals the cardinality of their union by Finset.card_union_of_disjoint. Rewriting replaces the sum on the left-hand side with this union.
uses
disjoint_sdiff_sdiff,Finset.card_union_of_disjointhave hdisj : Disjoint (codeword_supp x \ codeword_supp y) (codeword_supp y \ codeword_supp x) := disjoint_sdiff_sdiff rw [← Finset.card_union_of_disjoint hdisj]
It suffices to show that the union of the two set differences is a subset of the coordinates where x and y differ.
Unfolding the definition of hammingDist expresses it as the cardinality of the set of coordinates {i | x i ≠ y i}. By Finset.card_le_card, a subset has cardinality at most that of the ambient set, so the inequality on cardinalities reduces to the subset inclusion between the union and {i | x i ≠ y i}.
uses
Finset.card_le_cardunfold hammingDist apply Finset.card_le_card
For any index i in the union, either (x i ≠ 0 and y i = 0) or (y i ≠ 0 and x i = 0), and it suffices to show x i ≠ y i.
We take an arbitrary coordinate i in the union. Unfolding the definitions of union (Finset.mem_union), set difference (Finset.mem_sdiff), and codeword support (using Finset.mem_filter and Finset.mem_univ), and simplifying conjunctions with true_and, the membership hypothesis simplifies to saying that i is in the support of x but not y, or in the support of y but not x.
uses
Finset.mem_union,Finset.mem_sdiff,Finset.mem_filter,Finset.mem_univ,true_andintro i hi simp only [Finset.mem_union, Finset.mem_sdiff, codeword_supp, Finset.mem_filter, Finset.mem_univ, true_and] at hi ⊢
In either case, assuming x i = y i yields a contradiction, proving x i ≠ y i.
We split into the two cases of the disjunction. In the first case, x i ≠ 0 and ¬(y i ≠ 0); assuming x i = y i allows us to substitute y i for x i to obtain y i ≠ 0, contradicting ¬(y i ≠ 0). The second case is symmetric: y i ≠ 0 and ¬(x i ≠ 0); assuming x i = y i rewrites ¬(x i ≠ 0) to ¬(y i ≠ 0), contradicting y i ≠ 0. In both cases, this establishes x i ≠ y i.
rcases hi with ⟨h1, h2⟩ | ⟨h1, h2⟩ · intro heq rw [heq] at h1 exact h2 h1 · intro heq rw [heq] at h2 exact h2 h1
disjoint_sdiff_sdiff- For any two elements x and y in a generalized Boolean algebra (such as sets), the differences x \ y and y \ x are disjoint.
Finset.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_le_card- If a finite set s is a subset of a finite set t, then the cardinality of s is at most the cardinality of t.
Finset.mem_union- An element belongs to the union of two finite sets if and only if it belongs to the first set or the second set.
Finset.mem_sdiff- An element belongs to the difference s \ t of two finite sets if and only if it belongs to s and not to t.
Finset.mem_filter- An element belongs to the filtered set {x ∈ s | p x} if and only if it belongs to s and satisfies the predicate p.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set univ.
true_and- The conjunction of True with any proposition p is equivalent to p.
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.
/-- The sum of the sizes of the coordinate set differences of two codeword supports is at most their Hamming distance. -/theorem codeword_supp_diff_card_le_hammingDist {n : ℕ} {α : Type*} [DecidableEq α] [Zero α] (x y : Fin n → α) : (codeword_supp x \ codeword_supp y).card + (codeword_supp y \ codeword_supp x).card ≤ hammingDist x y := by have hdisj : Disjoint (codeword_supp x \ codeword_supp y) (codeword_supp y \ codeword_supp x) := disjoint_sdiff_sdiff rw [← Finset.card_union_of_disjoint hdisj] unfold hammingDist apply Finset.card_le_card intro i hi simp only [Finset.mem_union, Finset.mem_sdiff, codeword_supp, Finset.mem_filter, Finset.mem_univ, true_and] at hi ⊢ rcases hi with ⟨h1, h2⟩ | ⟨h1, h2⟩ · intro heq rw [heq] at h1 exact h2 h1 · intro heq rw [heq] at h2 exact h2 h1