Cardinality decomposition for symmetric difference
ProvedQuantumLTF.Majority.card_symmDiff_add_twice_intercombinatoricsfinite-setsfourier-analysissection-4
For finite sets and , their total cardinality with multiplicity decomposes into the symmetric difference and two copies of the intersection:
In particular, and have the same parity. This parity consequence is the finite-set step behind multiplication of Boolean Walsh characters.
Preamble
import Mathlib
Formal statement
namespace QuantumLTF.Majority
open scoped symmDiff
theorem card_symmDiff_add_twice_inter : ∀ {α : Type*} [Fintype α] [DecidableEq α] (A B : Finset α), (A ∆ B).card + 2 * (A ∩ B).card = A.card + B.card := by sorry
end QuantumLTF.MajoritySource
Elementary finite-set cardinality identity for symmetric difference.