Associativity of symmetric difference of sets

Solution 1:

You could use characteristic functions to make it more algebraic. Observe $$ 1_{A\cap B}=1_A\cdot 1_B \qquad\mbox{and}\qquad 1_{A\Delta B}=1_A+1_B-2\cdot 1_{A\cap B}. $$ Then $$ 1_{A\Delta(B\Delta C)}=1_A+1_{B\Delta C}-2\cdot1_{A\cap (B\Delta C)} $$ $$ =1_A+1_B+1_C-2\cdot1_{B\cap C}-2\cdot1_A\cdot(1_B+1_C-2\cdot1_{B\cap C}) $$ $$ =1_A+1_B+1_C-2\cdot1_{A\cap B}-2\cdot1_{B\cap C}-2\cdot1_{C\cap A}+4\cdot1_{A\cap B\cap C}. $$ I used that $\cap $ is associative to make sense of $A\cap (B\cap C)=A\cap B\cap C$. To be consistent, this can also be proven with characteristic functions: $$ 1_{A\cap(B\cap C)}=1_A1_{B\cap C}=1_A1_B1_C=1_{A\cap B}1_C=1_{(A\cap B)\cap C}. $$

Now starting from $1_{(A\Delta B)\Delta C}$, you end up with the same symmetric formula. Hence your two sets have the same characteristic functions, which means that they are equal.

Solution 2:

$A \oplus B$ contains those elements (of the given basic set) which belong to exactly one of the sets $A$ and $B$. Thus, $A \oplus (B \oplus C)$ consists of those elements which belong to exactly one of the sets $A$ and $B \oplus C$, i.e. to exactly one or all three of the sets $A$, $B$ and $C$. This shows $A \oplus (B \oplus C) = (A \oplus B) \oplus C$.

There is also a more algebraic proof, using the isomorphism of structures $(P(X),\oplus,\cap) \cong (\mathbb{F}_2^X,+,*)$, which immediately implies that $(P(X),\oplus,\cap)$ is a ring.