# Simple set exercise seems not so simple

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?

-
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

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.

-
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'$.

-
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)$$

-
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