10
$\begingroup$

By $A\oplus B$ we denote the symmectric difference of two sets. The definition is $A\oplus B =(A\setminus B) \cup (B\setminus A)$. Now I hope to show that $A\oplus (B\oplus C) = (A\oplus B)\oplus C$. I remember that there's an elegant proof, but I forget its detail. (The first step is to show $A\oplus (A\oplus B) = B$, and maybe applying this formula, we can obtain associativity.)

$\endgroup$
  • $\begingroup$ @julien: $\oplus$ is "XOR", which is the symmetric difference. It is not an unusual notation in some places. $\endgroup$ – Asaf Karagila Mar 17 '13 at 13:30
  • $\begingroup$ @AsafKaragila Ah, thanks a lot! I did not know that. $\endgroup$ – Julien Mar 17 '13 at 13:35
16
$\begingroup$

You could use characteristic functions to make it more algebraic. Observe $$ 1_{A\cap B}=1_A\cdot 1_B \qquad\mbox{and}\qquad 1_{A\Delta B}=1_A+1_B-2\cdot 1_{A\cap B}. $$ Then $$ 1_{A\Delta(B\Delta C)}=1_A+1_{B\Delta C}-2\cdot1_{A\cap (B\Delta C)} $$ $$ =1_A+1_B+1_C-2\cdot1_{B\cap C}-2\cdot1_A\cdot(1_B+1_C-2\cdot1_{B\cap C}) $$ $$ =1_A+1_B+1_C-2\cdot1_{A\cap B}-2\cdot1_{B\cap C}-2\cdot1_{C\cap A}+4\cdot1_{A\cap B\cap C}. $$ I used that $\cap $ is associative to make sense of $A\cap (B\cap C)=A\cap B\cap C$. To be consistent, this can also be proven with characteristic functions: $$ 1_{A\cap(B\cap C)}=1_A1_{B\cap C}=1_A1_B1_C=1_{A\cap B}1_C=1_{(A\cap B)\cap C}. $$

Now starting from $1_{(A\Delta B)\Delta C}$, you end up with the same symmetric formula. Hence your two sets have the same characteristic functions, which means that they are equal.

$\endgroup$
  • 1
    $\begingroup$ I think that this is a great method to prove such a thing! as it can be easily used to prove that $+$ is associative in boolean rings induced from boolean algebras as $+$ here represent the symmetric difference of elements in the boolean algebra. $\endgroup$ – Fawzy Hegab Jan 23 '15 at 10:33
  • $\begingroup$ Why is $1_{A\Delta B}= 1_A + 1_B - 1_{A \cap B}$? For $x\in A\cap B$, this function is $1 + 1 - 1 =1$, but $x \notin A \Delta B$? $\endgroup$ – Roland Jan 24 '16 at 10:27
  • 1
    $\begingroup$ @Roland It should be $\chi_{A\Delta B} = \chi_A + \chi_B -2\chi_{A\cap B}$. But goddamn...this proof idea is sexy as hell. $\endgroup$ – TheGeekGreek Sep 20 '16 at 22:33
8
$\begingroup$

$A \oplus B$ contains those elements (of the given basic set) which belong to exactly one of the sets $A$ and $B$. Thus, $A \oplus (B \oplus C)$ consists of those elements which belong to exactly one of the sets $A$ and $B \oplus C$, i.e. to exactly one or all three of the sets $A$, $B$ and $C$. This shows $A \oplus (B \oplus C) = (A \oplus B) \oplus C$.

There is also a more algebraic proof, using the isomorphism of structures $(P(X),\oplus,\cap) \cong (\mathbb{F}_2^X,+,*)$, which immediately implies that $(P(X),\oplus,\cap)$ is a ring.

$\endgroup$
  • 3
    $\begingroup$ You are missing the elements that are in all three of the sets $A, B, C$. In general, $\oplus A_{i}$ consists of the elements that belong to an odd number of $A_{i}$. $\endgroup$ – Andreas Caranti Mar 17 '13 at 13:20
  • $\begingroup$ Thank you. $\phantom{ }$ $\endgroup$ – Martin Brandenburg Mar 17 '13 at 13:31
2
$\begingroup$

Another way to prove this, is to first prove that $\;x \in A \oplus B \;\equiv\; x \in A \not\equiv x \in B\;$, and then use the analogous law of logic ($\;\not\equiv\;$ is associative, i.e. $\;P \not\equiv (Q \not\equiv R) \;\equiv\; (P \not\equiv Q) \not\equiv R\;$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy