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.

Exercise about sets from Birkhoff's "Modern Applied Algebra".

Prove that for operation $\ \Delta $ , defined as

$\ R \Delta S = (R \cap S^c) \cup (R^c \cap S) $

following is true:

$\ R \Delta ( S \Delta T ) = ( R \Delta S ) \Delta T $

($\ S^c $ is complement of $\ S $)

It's meant to be very simple, being placed in the first excercise block of the book. When I started to expand both sides of equations in order to prove that they're equal, I got this monster just for the left side:

$\ R \Delta ( S \Delta T ) = \Bigl( R \cap \bigl( (S \cap T^c) \cup (S^c \cap T) \bigr)^c \Bigr) \cup \Bigl(R^c \cap \bigl( (S \cap T^c) \cup (S^c \cap T) \bigr) \Bigr) $

For the right:

$\ ( R \Delta S ) \Delta T = \Bigl(\bigl( (R \cap S^c) \cup (R^c \cap S) \bigr) \cap T^c \Bigr) \cup \Bigl( \bigl( (R \cap S^c) \cup (R^c \cap S) \bigr)^c \cap T \Bigr) $

I've tried to simplify this expression, tried to somehow rearrange it, but no luck. Am I going the wrong way? Or what should I do with what I have?

share|improve this question
    
I usually prefer to mark the complement as $\cdot^c$ as $'$ and $\bar\cdot$ have way too many uses. Also, as joriki mentioned the $+$ is the symmetric difference which many mark by $\Delta$. –  Asaf Karagila Apr 23 '11 at 9:47

3 Answers 3

up vote 6 down vote accepted

This is the symmetric difference. It includes all elements that are in exactly one of the two sets. In binary terms, it's the XOR operation. Independent of the order of the operations on the three sets, the result will contain exactly the elements that are in an odd number of the sets.

share|improve this answer
    
Thank you. Just found proof on ProofWiki: proofwiki.org/wiki/Symmetric_Difference_is_Associative –  furikuretsu Apr 23 '11 at 9:07
    
Reading your answer, I thought those four sentences were exactly the four right points to mention. +1. –  Did Apr 23 '11 at 9:12
    
Nice answer! –  Rudy the Reindeer Apr 23 '11 at 9:15

joriki's answer it the best way to understand this conceptually. Still, it's perfectly possible to continue formally the way you started: simply repeatedly apply De Morgan's laws:

$(A \cup B)' = A' \cap B'$ and $(A \cap B)' = A' \cup B'$.

share|improve this answer
    
Thank you. Now I realise that I've just gave up with formal derivation too easily. –  furikuretsu Apr 23 '11 at 9:09

You're doing the right thing. I just did it just to check.

As a hint: you can transform either side into $$ (R \cap S^c \cap T^c) \cup (R\cap S \cap T) \cup (R^c \cap S \cap T^c) \cup (R^c \cap S^c \cap T) $$

share|improve this answer
1  
To connect the answers: This is the union of the set of all elements contained in all three sets with the three sets of elements contained in exactly one set. –  joriki Apr 23 '11 at 9:17

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.