Associativity of symmetric set difference

Question

The symmetric difference $A$ $\Delta$ $B$ of $A$ and $B$ is defined as $(A - B) \cup (B - A)$. (The set of elements that belong to $A$ or $B$ but not both.)

(a) Construct a truth table to show that $\Delta$ is associative.

(b) Show that $x$ belongs to $A$ $\Delta$ $(B$ $\Delta$ $C)$ if and only if $x$ belongs to an odd number of the sets $A$, $B$ and $C$ and use this observation to give a second proof that $\Delta$ is associative.

For part (a), I'd be grateful is someone could post the full truth table, as I'm not entirely sure what column headings they are looking for.

For part (b), this is what I did:

(For the left to right implication) Let $x \in $ $A$ $\Delta$ $(B$ $\Delta$ $C)$. Then, by the definition of $\Delta$, we have either $x \in $ $A$ or $x \in $ $(B$ $\Delta$ $C)$ but not both. So if $x \in A$ then either it is not in $B$ nor $C$ or it is in both $B$ and $C$. So here $x$ can be in just $A$, or in $A, B$ and $C$. If $x \in (B$ $\Delta$ $C)$, then $x \notin A$. So by a similar logic $x$ can be in $B$ or $C$, but not both. The implication works both ways, hence the 'iff'.

However, I'm not sure how this proves associativity. I tried to write it as

$A$ $\Delta$ $(B$ $\Delta$ $C)$ = ($A$ $\Delta$ $B$) $\cap$ ($A$ $\Delta$ $C$) $\cap$ ($B$ $\Delta$ $C$) $ \cup$ $ (A\cap B\cap C)$ And then associativity would follow by swapping $A$ and $C$ but I'm not sure if this is the right way of doing it.

Answer 1

Here is a truth table with an intermediate column;

$$\ \begin{array}{|ccc|c|c|} \hline A&B&C&A\Delta B&(A\Delta B)\Delta C\\ \hline 0&0&0&0&0\\ 0&0&1&0&1\\ 0&1&0&1&1\\ 0&1&1&1&0\\ 1&0&0&1&1\\ 1&0&1&1&0\\ 1&1&0&0&0\\ 1&1&1&0&1\\ \hline \end{array}$$

It remains to do a similar array with $A \Delta (B\Delta C)$ and see they have similar last columns.

---

A completely different method (afterthought... 6 years later):

In fact, if one uses the equivalent boolean formulation with XOR (eXclusive OR) operator, one can easily check that the following function:

$$XOR(x,y)=x(1-y)+y(1-x)=x+y-2xy$$

is such that

$$XOR(0,0)=0, \ \ XOR(0,1)=1, \ \ XOR(1,0)=1, \ \ XOR(1,1)=0$$

i.e., "works" like the $\Delta$ operator.

It is now routine calculation to show thay

$$XOR(XOR(a,b),c)=XOR(a+b-2ab,c)=(a+b-2ab)+c-2(a+b-2ab)c$$

Finally:

$$XOR(XOR(a,b),c)=a+b+c-2(ab+bc+ca)+4abc\tag{1}$$

which is a symmetrical expression in variables $a,b,c$.

It is routine verification that $XOR(a,XOR(b,c))$ gives the same result as (1).

Answer 2

Consider the representation, $(a,b)\in \mathbb F_2\times \mathbb F_2$
if $x\in A$, then $a=1$ otherwise $a=0$

for example,if $x\in A$ but $x\notin B$

then $x\mapsto(1,0)$, define exist function: $[ a,b]=a+b$

and $x\in A\Delta B\Leftrightarrow [a,b]=1$

and you can view $(A\Delta B)\Delta C $ as$[[a,b],c]=(a+b)+c=a+(b+c)=[a,[b,c]]$

So, $x\in (A\Delta B)\Delta C\Leftrightarrow x\in A\Delta(B\Delta C)$

Actually, $(P(S),\Delta,\cap)$ is a Ring, and you can prove the distribution law as follow.

Consider the exist fuction like $x\in (A\Delta B)\cap C\Leftrightarrow (a+b)\times c=0\Leftrightarrow ac+bc=0\Leftrightarrow x\in (A\cap C)\Delta (B\cap C)$