Why is the following statement true about symmetric differences of Subsets?

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?

Solution 1:

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

Solution 2:

Note that the symmetric difference is to sets as what the $XOR$ ($\oplus$) operation is to claims. And, when it comes to the $XOR$, we know that $A \oplus B$ is true iff exactly one of $A$ and $B$ is true. Put differently: the one being true will exclude the other one being true.

This thinking, however, does not generalize the way people think it does. That is: many people believe that the $XOR$ generalizes to multiple claims as follows: $A \oplus B \oplus C$ is true iff exactly one of $A$, $B$, and $C$ is true: the one being true excludes the others from being true.

However, this intuition is mistaken: if $A$, $B$, and $C$ are all true, then $A \oplus B \oplus C$ is also true. Indeed, what does turn out to be the case, is that a generalized $XOR$ is true if and only if an odd number of the claims are true.

I believe that many people think about symmetric difference the same way, i.e. that $x \in A \Delta B \Delta C$ if and only $x$ is in exactly one of the three sets $A$, $B$, and $C$. However, as with the $XOR$, this intuition is not true: $x$ is also an element of $A \Delta B \Delta C$ if $x$ is an element of all three sets. And again, it turns out that $x \in X_1 \Delta X_2 \Delta ... \Delta X_n$ iff $x$ is an element of exactly an odd number of the sets $X_1 \Delta X_2 \Delta ... \Delta X_n$

As the other answers indicate, this is easily proven using induction. But I just wanted to address the intuition.

Solution 3:

We can prove this is true by induction on $m$, the case case $m=2$ being easy to check. It can also make sense to have $m=1$ be the base case.

\begin{align} &x\in A_1 \Delta A_2 \Delta \cdots \Delta A_m \\\\\iff &x\in (A_1\Delta \cdots \Delta A_{m-1})\Delta A_m \tag1 \\\\\iff &x\in (A_1\Delta \cdots \Delta A_{m-1})\text{ and } x\notin A_m \\&\hspace{3cm}\text{or}\quad \tag2\\ &x\notin (A_1\Delta \cdots \Delta A_{m-1})\text{ and } x\in A_m \\\\\stackrel{\text{IHOP}}\iff &x\in (\text{an odd # of $A_1,\dots,A_{m-1}$})\text{ and } x\notin A_m \\&\hspace{3cm} \text{or}\quad \tag3\\ &x\in (\text{an even # of $A_1,\dots,A_{m-1}$})\text{ and } x\in A_m \\\\ \iff & x\in \text{an odd # of $A_1,\dots,A_m$}\tag 4 \end{align}

Explanations: