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.

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

share|improve this question
1  
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
add comment

5 Answers

up vote 10 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
2  
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
add comment

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.

share|improve this answer
add comment

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 ;-)

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

I would simply calculate the elements in the set on the left hand side, as follows:

\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}

By set extensionality this proves the original statement.

share|improve this answer
add comment

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.