# Prove $(A \triangle B) \cap (B\triangle C) \cap (C\triangle A) = \emptyset$

This can be proved by assuming that there exists some $x \in (A \triangle B) \cap (B\triangle C) \cap (C\triangle A)$ and then deriving a contradiction by considering each of the cases that arise.

[$X\triangle Y$ is the symmetric difference of $X$ and $Y$]

Now, this proof ultimately breaks down into six cases which makes it a bit long considering the simple goal. So I was wondering if there was a better way of doing this?

My six case proof goes something like this:

Suppose to the contrary that $x \in (A \triangle B) \cap (B\triangle C) \cap (C\triangle A)$. Then $x \in (A \triangle B)$ and $x \in (B \triangle C)$ and $x \in (C\triangle A)$. Since $x \in (C \triangle A)$, $x \in A\backslash C$ or $x \in C\backslash A$.

Case 1: $x \in A\backslash C$. Since $x \in (B \triangle C)$, $x \in B\backslash C$ or $x \in C\backslash B$. Case 1.1: $x\in B\backslash C$...

Case 2: $x \in C\backslash A$. Since $x \in (B \triangle C)$, $x \in B\backslash C$ or $x \in C\backslash B$. Case 2.1: $x\in B\backslash C$...

-
By symmetry there is only one case. Suppose $x$ is in the first symmetric difference. Without loss of generality $x$ is in $A$ but not in $B$. so by the second term it is in $C$, which contradicts the last symmetric difference. –  André Nicolas Apr 6 '13 at 16:04

In principle there are two cases, but symmetry brings it down to one.

Suppose $x$ is in our set. Then $x$ is in $A\triangle B$. Without loss of generality we may assume that $x$ is in $A$ but not in $B$.

So since $x$ is in $B\triangle C$, we conclude that $x$ must be in $C$. But then $x$ cannot be in $A\triangle C$. So our set is empty.

-

Indicator functions are perhaps a good way to go if you want to avoid cases or symmetry arguments. First prove that $$\chi_{A \triangle B} = (\chi_A+\chi_B \bmod 2)$$ Then show that if $S = (A \triangle B) \cap (B \triangle C) \cap (C \triangle A)$ then we have \begin{align} \chi_S &= (\chi_A+\chi_B)(\chi_B+\chi_C)(\chi_C+\chi_A) \bmod 2 \\ &= \chi_A\chi_B\chi_C + \chi_A^2\chi_B+\chi_A^2\chi_C+\chi_A^2\chi_C\\ & \qquad +\chi_B^2\chi_C+\chi_B^2\chi_A+\chi_B\chi_C^2+\chi_B\chi_C\chi_A \bmod 2 \\ &= \chi_A\chi_B\chi_C + \chi_A\chi_B + \chi_A\chi_C+\chi_A\chi_C \\ & \qquad +\chi_B\chi_C + \chi_B\chi_A + \chi_B \chi_C + \chi_B\chi_C\chi_A \bmod 2\\ &= 2(\chi_A\chi_B\chi_C + \chi_A\chi_B + \chi_A\chi_C + \chi_B\chi_C) \bmod 2 \\ &= 0 \end{align}

-
Actually, we can just work $\mod 2$ so ${\bf 1}_{A\triangle B}\equiv {\bf 1 }_A+{\bf 1 }_B$, right? Maybe it makes calculations shorter. –  Pedro Tamaroff Apr 6 '13 at 16:16
@PeterTamaroff: D'oh, I learnt that trick in my first year, should have used that... thanks! I'll update the answer now. –  Clive Newstead Apr 6 '13 at 16:18

It's possible to make only one case. Because $$x\in (A \triangle B)\iff (x\in A \wedge x\notin B ) \vee (x\notin A \wedge x\in B)$$

Then we have $$x\in (A\triangle B) \cap (B\triangle C) \cap (C\triangle A)$$ using the definition above we see that $x$ can't be in $A,B$ or $C$. Hence the intersection is empty.

-

Your equality $$(A \triangle B) \cap (B\triangle C) \cap (C\triangle A) = \varnothing \tag{\clubsuit}$$

can be interpreted as: $$\color{blue}{for\ any\ three\ numbers,\ some\ two\ have\ the\ same\ parity,}$$ which is obviously true. To get the details, you can consider $\clubsuit$ element-wise and translate into logic, that is, it is equivalent to $$(x_A \oplus x_B) \land (x_B \oplus x_C) \land (x_C \oplus x_A) = \mathtt{false}.$$

However, the last equality might be interpreted in $\mathbb{Z}_2$, that is, in numbers modulo 2. From this perspective we get $$(y_A + y_B)(y_B + y_C)(y_C+y_A) \equiv 0 \pmod 2 \tag{\spadesuit}$$ for any $y_A,y_B,y_C \in \mathbb{Z}$. But $\spadesuit$ literally means: some two of any three numbers have same parity, and this concludes the proof.

I hope this helps ;-)

-
Very nice. Working modulo makes things much easier! –  Pedro Tamaroff Apr 6 '13 at 16:36
@PeterTamaroff Yeah, it does. When I approach XOR, I immediately think of $\mathbb{F}_2$ field. I've just noticed, that because of your comment the old Clive's answer looks now almost exactly like mine :-P –  dtldarek Apr 6 '13 at 16:41
\begin{align} & x \in (A \triangle B) \cap (B\triangle C) \cap (C\triangle A) \\ \equiv & \;\;\;\;\;\text{"expand definition of $\;\cap\;$ twice, and of $\;\triangle\;$ three times"} \\ & (x \in A \not\equiv x \in B) \land (x \in B \not\equiv x \in C) \land (x \in C \not\equiv x \in A) \\ \equiv & \;\;\;\;\;\text{"rewrite third part to $\;x \in C \equiv x \not\in A\;$; use that to substitute in second part"} \\ & (x \in A \not\equiv x \in B) \land (x \in B \not\equiv x \not\in A) \land (x \in C \equiv x \not\in A) \\ \equiv & \;\;\;\;\;\text{"simplify second part to $\;x \in B \equiv x \in A\;$; use that to substitute in first part"} \\ & (x \in A \not\equiv x \in A) \land (x \in B \equiv x \in A) \land (x \in C \equiv x \not\in A) \\ \equiv & \;\;\;\;\;\text{"first part is false"} \\ & \textrm{false} \\ \equiv & \;\;\;\;\;\text{"definition of $\;\emptyset\;$"} \\ & x \in \emptyset \\ \end{align}