DecisionTree.symmDiff_singleton_invol
theoremverifiedimported Lean
Symmetric difference with a singleton is an involution. Fix $n \in \bbn$ and an index $i \in \{0, 1, \dots, n-1\}$. The map on subsets of $\{0, 1, \dots, n-1\}$ that sends each set $S$ to its symmetric difference $S \triangle \{i\}$ with the singleton $\{i\}$ is an involution: applying it twice returns every set to itself, so $\bigl(S \triangle \{i\}\bigr) \triangle \{i\} = S$ for all $S$.
Statement
variable {n : ℕ} in lemma DecisionTree.symmDiff_singleton_invol (i : Fin n) : Function.Involutive (fun S : Finset (Fin n) => symmDiff S {i})
- Source
- TCSlib, `DecisionTree.symmDiff_singleton_invol`
- 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.DecisionTree.symmDiff_singleton_invol← DecisionTree.symmDiff_singleton_invol (TCSlib/BooleanAnalysis/LMN/DecisionTreeFourier.lean:64): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- DecisionTree.sum_symmDiff_reindexInvariance 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…
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.
variable {n : ℕ} inlemma DecisionTree.symmDiff_singleton_invol (i : Fin n) : Function.Involutive (fun S : Finset (Fin n) => symmDiff S {i}) := fun S => by simp only [symmDiff_assoc, symmDiff_self, symmDiff_bot]