# Basic properties of symmetric difference in sets: $A \Delta B=A \Delta D$ implies $B=D$

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
Related question: math.stackexchange.com/questions/537172/… – Martin Sleziak Aug 30 '14 at 15:26

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\Delta 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 $\Delta$ 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$$

-

\newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \text{"#2"} \\ \quad & } \newcommand{\endcalc}{\end{align}}As a first simplification, we can take out $\;C\;$ and rephrase your theorem as $$\tag{0} A \Delta B = A \Delta D \;\Rightarrow\; B = D$$

The proof depends on your definition and the laws of logic that are available.

In my favorite setting the proof would go something like this:

$$\calc A \Delta B = A \Delta D \calcop{\equiv}{set extensionality; definition (1) of \;\Delta\;, below, twice} \langle \forall x :: x \in A \not\equiv x \in B \;\equiv\; x \in A \not\equiv x \in D \rangle \calcop{\equiv}{logic: \;\equiv\; is symmetric} \langle \forall x :: x \in A \not\equiv x \in A \;\equiv\; x \in B \not\equiv x \in D \rangle \calcop{\equiv}{logic: \;\not\equiv\; is anti-reflexive} \langle \forall x :: \text{false} \;\equiv\; x \in B \not\equiv x \in D \rangle \calcop{\equiv}{logic: the negation of \;\not\equiv\; is \;\equiv\;} \langle \forall x :: x \in B \equiv x \in D \rangle \calcop{\equiv}{set extensionality} B = D \endcalc$$

This completes the proof of (a slightly stronger version of) $(0)$.

Above we used the fact (or alternative definition) that for every $\;x\;$ $$\tag{1} x \in X \Delta Y \;\equiv\; x \in X \not\equiv x \in Y$$

Also, we implicitly used the fact that $\;\equiv\;$ and $\;\not\equiv\;$ are not only both associative but also mutually associative.

-