Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
You might have a look at (answers to) these questions: Neat solutions to tedious questions, Symmetric Difference Identity and Relation between XOR and Symmetric difference. –  Martin Sleziak Apr 7 '12 at 18:04
    
The simplest proof, for me, is using characteristic functions, but this surely beats it :) –  Beni Bogosel Apr 7 '12 at 18:11
    
@KannappanSampath The problem is that part of proving that that is a ring you prove this associtivity... –  N. S. Apr 7 '12 at 19:02
1  
@N.S. I think I had it wrong. I deleted them. Arturo's answer expands the hint...IMO. –  user21436 Apr 7 '12 at 19:14

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
1  
Looks like this is what the hint says and not what I assumed. My hint was more misleading than helpful, I think. +1. –  user21436 Apr 7 '12 at 19:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.