3
$\begingroup$

I can prove associativity of symmetric difference of sets using it's definition $A \triangle B = (A \backslash B)\cup(B \backslash A)$.

But in the text I read author gives a hint to derive it somehow from associativity of addition in $\mathbb{Z}_2$. I can't see any clear analogy.

Update: clear analogy is given in the comment section below.

  • 3
    You might have a look at (answers to) these questions: [Neat solutions to tedious questions](http://math.stackexchange.com/questions/100747/neat-solutions-to-tedious-questions), [Symmetric Difference Identity](http://math.stackexchange.com/questions/52801/symmetric-difference-identity) and [Relation between XOR and Symmetric difference](http://math.stackexchange.com/questions/84184/relation-between-xor-and-symmetric-difference).2012-04-07
  • 0
    The simplest proof, for me, is using characteristic functions, but this surely beats it :)2012-04-07
  • 0
    @KannappanSampath The problem is that part of proving that that is a ring you prove this associtivity...2012-04-07
  • 1
    @N.S. I think I had it wrong. I deleted them. Arturo's answer expands the hint...IMO.2012-04-07

1 Answers 1

5

You can identify subsets of $X$ with their characteristic functions taking values on $\mathbb{Z}_2$; union of subsets corresponds to the pointwise $\max$ operator of characteristic functions, intersection of subsets to the pointwise product, and symmetric difference to the pointwise addition. So the properties of the symmetric difference corresponds to the properties of the pointwise addition of characteristic functions. This gives $$\begin{align*}\text{associativity of symmetric difference}&\iff \text{associativity of pointwise addition of functions}\\ &\iff \text{associativity of addition in the codomain}. \end{align*}$$

  • 1
    Looks like this is what the hint says and not what I assumed. My hint was more misleading than helpful, I think. +1.2012-04-07