2
$\begingroup$

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?

  • 0
    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$.2011-04-23

3 Answers 3

6

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.

  • 0
    Nice answer!2011-04-23
3

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

  • 0
    Thank you. Now I realise that I've just gave up with formal derivation too easily.2011-04-23
2

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

  • 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.2011-04-23