AFTD Auto-Formalizing Theoretical Domains

DecisionTree.sum_symmDiff_reindex

theoremverifiedimported Lean

Invariance of a subset-sum under symmetric difference with a point. Fix $n \in \bbn$, let $i$ be an element of $\{0, 1, \dots, n-1\}$, and let $g$ assign a real number to each subset of $\{0, 1, \dots, n-1\}$. Then summing $g$ over all subsets is unaffected by first toggling the membership of $i$; that is, \[ \sum_{S} g\big(S \mathbin{\triangle} \{i\}\big) = \sum_{S} g(S), \] where both sums range over all subsets $S \subseteq \{0, 1, \dots, n-1\}$ and $S \mathbin{\triangle} \{i\}$ denotes the symmetric difference of $S$ with the singleton $\{i\}$.

Statement

variable {n : ℕ} in
lemma DecisionTree.sum_symmDiff_reindex (g : Finset (Fin n) → ℝ) (i : Fin n) :
    ∑ S : Finset (Fin n), g (symmDiff S {i}) = ∑ S : Finset (Fin n), g S
Source
TCSlib, `DecisionTree.sum_symmDiff_reindex`
Lean proof
By Hydroxyi, Owen McGinty, Seyoon Ragavan (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

Lean source view module on GitHub

variable {n : ℕ} in
/-- Reindexing a sum over all frequencies by the involution `S ↦ S ∆ {i}`. -/
lemma DecisionTree.sum_symmDiff_reindex (g : Finset (Fin n) → ℝ) (i : Fin n) :
    ∑ S : Finset (Fin n), g (symmDiff S {i}) = ∑ S : Finset (Fin n), g S :=
  Fintype.sum_bijective _ ((symmDiff_singleton_invol i).bijective) _ _ (fun _ => rfl)
See it in the graphDiscuss this resultChallenge it