AFTD Auto-Formalizing Theoretical Domains

codeword_supp_diff_card_le_hammingDist

theoremverified

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

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.

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

    lines 5–7

    uses disjoint_sdiff_sdiff, Finset.card_union_of_disjoint

      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]
  2. 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}.

    lines 8–9

    uses Finset.card_le_card

      unfold hammingDist
      apply Finset.card_le_card
  3. 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.

    lines 10–12

    uses Finset.mem_union, Finset.mem_sdiff, Finset.mem_filter, Finset.mem_univ, true_and

      intro i hi
      simp only [Finset.mem_union, Finset.mem_sdiff, codeword_supp, Finset.mem_filter, Finset.mem_univ,
        true_and] at hi ⊢
  4. 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.

    lines 13–19

      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

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