Let $X$ be a non-empty set. Then, for a finite amount of subsets $A_1, A_2, …,A_m \in X$ we define $S := A_1 \Delta A_2 \Delta … \Delta A_m$ as the symmetric difference of all $A_k$ with $ k \in I:= [1,…,m]$
Then:
A point $x\in X$ is element of S, when x is element of an odd index number k of $A_k$
So, when the Quantity of Indices $ k \in {1,…,m} $ with $ x\in A_k$ is odd.
why is this statement true? I mean x can be in the intersection of 3 subsets of $X$ and wouldn't be in the symmetric difference. Is there something I am not noticing?
Best Answer
In writing $A_1\Delta A_2\Delta\ldots\Delta A_m$ you are implicitly assuming that the binary operation $\Delta$ is associative, so let's check this first. An element $x$ is in $(A\Delta B)\Delta C$ if it is in exactly one of $A\Delta B$ or $C$. Which means that $x$ is in $C$ and not in $A\Delta B$ or that $x$ is in $A\Delta B$ and not in $C$. In the first of these cases either $x$ is in $C$ and in neither $A$ nor $B$, or $x$ is in $C$ and in both $A$ and $B$, which is to say that $x$ is in all three of $A$, $B$, $C$. In the second case $x$ is in exactly one of $A$ or $B$ and not in $C$. You can see that the four situations we end up with correspond exactly to "$x$ in an odd number of the sets $A$, $B$, $C$". We wanted to check that this is the same for $A\Delta(B\Delta C)$, but since the result we just got is symmetric under permutation of $A$, $B$, $C$ and since $\Delta$ is commutative, we can already see that the result will be the same. So associativity is proved and, furthermore, we have established the property that you were trying to understand.
To prove that the result holds for symmetric differences of more than three sets, you can use induction. Let $S$ be the symmetric difference of sets $A_1$, $A_2$, ..., $A_m$ and take the induction hypothesis to be that $x\in S$ is equivalent to $x$ being in exactly an odd number of these $m$ sets. Then $x\in S\Delta A_{m+1}$ if $x\in S$ and $x\notin A_{m+1}$ or if $x\notin S$ and $x\in A_{m+1}$. In the first case $x$ in in an odd number of the $A_1$, $A_2$, ..., $A_m$ and not in $A_{m+1}$; in the second case $x$ is in and even number of the $A_1$, $A_2$, ..., $A_m$ and also in $A_{m+1}$. In either case $x$ is in an odd number of the $A_1$, $A_2$, ..., $A_{m+1}$.