AFTD Auto-Formalizing Theoretical Domains

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

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