Home > Problem Solving, Set Theory > Symmetric difference is associative

## Symmetric difference is associative

I’m sure that any mathematics university student came across in the first years of university, in some course of set theory, to proving the fact that the difference symmetric operation is associative:

$A \Delta (B \Delta C)= (A\Delta B)\Delta C$

where $A \Delta B=(A\setminus B) \cup (B\setminus A)=(A\cup B)\setminus (A \cap B)$.

There are a few ways to do this. First there is the direct way using double inclusion: choose $x$ in the LHS member of the equality and prove that it is also in the RHS member. This is probably the longest method around, but it can be done.

The second method beats the first one at high score. Using characteristic functions, it is very easy to express the characteristic function of each of the LHS or RHS in thems of the characteristic functions of $A,B,C$, and see that the result is the same.

The third method, mentioned in the following article of Halmos: DOES MATHEMATICS HAVE ELEMENTS? makes fun of both methods described above. It uses again the characteristic function, but in a totally different way. Note that $\chi_{A\Delta B}=\chi_A+\chi_B \mod 2$, and we are done, since by using the associativity of the integers $\mod 2$ we find that

$\chi_{A\Delta (B\Delta C)}=\chi_{(A\Delta B)\Delta C} \mod 2$

and the equality modulo $2$ of two functions taking only values $0$ and $1$ implies their equality.