Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 at 15:26

6 Answers 6

up vote 6 down vote accepted

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.

share|improve this answer

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?

share|improve this answer
    
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$.

share|improve this answer

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

share|improve this answer
    
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$$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.