symmetric difference of sets

Printable View

December 1st 2009, 07:20 PM
santiagos11

symmetric difference of sets

prove that for sets $A,B,C,D$
$A \Delta B = C \Delta D$ if and only if $A \Delta C = B \Delta D$
December 1st 2009, 09:11 PM
Drexel28

Quote:

Originally Posted by santiagos11

prove that for sets $A,B,C,D$
$A \Delta B = C \Delta D$ if and only if $A \Delta C = B \Delta D$

What have you tried? Although there are many I think that the definition of symmetric difference best suited to this case is $A\Delta B=\left(A\cup B\right)-\left(A\cap B\right)$ .
December 2nd 2009, 04:47 AM
emakarov

There is also a different way to solve this that sometimes works very well with symmetric difference.

Define the function $in$ by $in(x,A)=1$ if $x\in A$ and $in(x,A)=0$ if $x\notin A$ . Here $A$ is any set and $x$ is any object.

Also, define the function $\oplus:\{0,1\}\times\{0,1\}\to\{0,1\}$ as follows:
$0\oplus0=0$
$0\oplus1=1$
$1\oplus0=1$
$1\oplus1=0$
(If we associate 1 with True and 0 with False, then $x\oplus y=\neg(x\leftrightarrow y)$ . Also, $\oplus$ is addition modulo 2.) One can check that $\oplus$ is commutative and associative.

Show that $in(x,A\triangle B)=in(x,A)\oplus in(x,B)$ for all $A$ , $B$ , and $x$ .

The part above was generic; it applies to any problem with symmetric difference and has to be done only once.

Now, from this problem's assumption and the fact above we have $in(x,A)\oplus in(x,B)=in(x,C)\oplus in(x,D)$ for all $x$ . We can add (using $\oplus$ ) an expression $in(x,E)$ to both sides where $E$ is $A$ , $B$ , $C$ , or $D$ . E.g., if we add $in(x,B)$ to both sides, we get $in(x,A)$ = $in(x, C)\oplus in(x,D)\oplus in(x,B)$ . From here it is easy to show the desired equation.
December 2nd 2009, 05:05 AM
Grandad

1 Attachment(s)

Hello santiagos11

Quote:

Originally Posted by santiagos11

prove that for sets $A,B,C,D$
$A \Delta B = C \Delta D$ if and only if $A \Delta C = B \Delta D$

I think this is easiest to prove by re-writing it as the equivalent statement using logical propositions. In other words:
Prove that if $a, b,c, d$ are logical propositions, then $a \oplus b \equiv c \oplus d$ if and only if $a \oplus c \equiv b \oplus d$ , where $\oplus$ denotes 'exclusive or'.

This is quite straightforward if you use a Truth Table for each of the compound propositions and show that each table produces an identical output.

The attached diagram shows the truth table for $a \oplus b \equiv c \oplus d$ . It is a simple matter to show that the table for $a \oplus c \equiv b \oplus d$ produces the same result.

Grandad