# Basic properties of symmetric difference in sets

How can I prove that for any sets $A,B,C,D$
if $$A \Delta B = C$$ and
$$A \Delta D = C$$ then $B=D$.
Where $\Delta$ denotes symmetric difference.

-
Sorry, I mixed it up with something else. –  Ishan Banerjee Feb 4 '13 at 12:40

First show that $\Delta$ is associative and has inverses; namely, every set is its own inverse. Then apply $A$ from the left to both equations and use what you proved in the first step. In doing this, it may help to think of the symmetric difference as XOR.

-

The probabilist in me cannot resist mentioning that symmetric differences can (and maybe they should) be approached through indicator functions modulo 2.

Recall that, for every $A\subseteq E$, the indicator function $\mathbf 1_A$ is defined on $E$ by $\mathbf 1_A(x)=1$ if $x$ is in $A$ and $\mathbf 1_A(x)=0$ if $x$ is in $E\setminus A$.

Then, for every subsets $A$ and $B$ of $E$, the set $C=A\triangle B$ is uniquely characterized by the fact that $\mathbf 1_C=\mathbf 1_A+\mathbf 1_B\pmod{2}$ (can you check this?).

A host of properties of $\triangle$ become obvious with this approach since $\Delta$ is simply the sum in the group $\mathbb Z/2\mathbb Z$. For example, your hypothesis is that $\mathbf 1_A+\mathbf 1_B=\mathbf 1_C=\mathbf 1_A+\mathbf 1_D\pmod{2}$ hence $\mathbf 1_B=\mathbf 1_D\pmod{2}$. And this is enough to guarantee that $B=D$ (can you check this?).

Note equivalently that, in every group $(G,\ast)$, the identity $g\ast h_1=g\ast h_2$ for some $g$, $h_1$ and $h_2$ in $G$ implies that $g^{-1}\ast g\ast h_1=g^{-1}\ast g\ast h_2$ hence $h_1=h_2$. Homework: what is $g^{-1}$ in the setting of the exercise?

-
Seems an expansion of @joriki's suggestion to see $\triangle$ as XOR. –  Did Feb 4 '13 at 12:49

Assume $x$ is in $B$, and deduce from the given equations that it must also be in $D$. Then assume it's in $D$, and deduce by symmetry that it's in $B$. That will prove $B=D$.

-

Take $b\in B$:

1.: $b\notin A$. This means that $b\in C\setminus A=D\setminus A$ and hence in $D$.

2.: $b\in A$. This means that $b\in A\setminus C=A\cap D$ and hence in $D$.

This proves that $B\subseteq D$ and for the other inclusion just swap $B$ and $D$.

-
How do you know that $C\setminus A = D\setminus A$ ? –  Sunny88 Feb 4 '13 at 12:44
@Sunny88: $A\Delta D= C$ are the elements that are either in $A$ or $D$ but not in both. So if $c\in A\Delta D$ but not in $A$ it must be in $D$ (and still not in $A$, so it's in $D\setminus A$). –  Michalis Feb 4 '13 at 12:53
$$B=\emptyset\Delta B=(A\Delta A)\Delta B=A\Delta(A\Delta B)=A\Delta C=A\Delta(A\Delta D)=(A\Delta A)\Delta D=\emptyset\Delta D=D$$