properties of symmetric difference

Recall that the symmetric difference of two sets $A,B$ is the set $A\cup B-(A\cap B)$ . In this entry, we list and prove some of the basic properties of $\symd$ .

1. (commutativity of $\symd$ ) $A\symd B=B\symd A$ , because $\cup$ and $\cap$ are commutative.
2. If $A\subseteq B$ , then $A\symd B=B-A$ , because $A\cup B= B$ and $A\cap B =A$ .
3. $A\symd \varnothing = A$ , because $\varnothing \subseteq A$ , and $A-\varnothing=A$ .
4. $A\symd A=\varnothing$ , because $A\subseteq A$ and $A-A=\varnothing$ .
5. $A\symd B=(A-B)\cup (B-A)$ (hence the name symmetric difference).
   Proof. $A\symd B= (A\cup B)-(A\cap B)= (A\cup B)\cap (A\cap B)'= (A\cup B)\cap (A'\cup B')= ((A\cup B)\cap A')\cup ((A\cup B)\cap B')= (B\cap A')\cup (A\cap B')= (B-A)\cup (A-B)$ .
6. $A'\symd B'=A\symd B$ , because $A'\symd B'=(A'-B')\cup (B'-A')=(A'\cap B)\cup (B'\cap A)=(B-A)\cap (A-B)=A\symd B$ .
7. (distributivity of $\cap$ over $\symd$ ) $A\cap (B\symd C)=(A\cap B)\symd (A\cap C)$ .
   Proof. $A\cap (B\symd C) = A\cap ((B\cup C)-(B\cap C))$ , which is $(A\cap (B\cup C))-(A\cap (B\cap C))$ , one of the properties of set difference (see proof here). This in turns is equal to $((A\cap B)\cup (A\cap C))-((A\cap B)\cap (A\cap C)) = (A\cap B)\symd (A\cap C)$ .
8. (associativity of $\symd$ ) $(A \symd B) \symd C = A \symd (B \symd C)$ .
   Proof. Let $U$ be a set containing $A,B,C$ as subsets (take $U=A\cup B\cup C$ if necessary). For a given $B$ , let $f:P(U)\times P(U)\to P(U)$ be a function defined by $f(A,C)= (A\symd B)\symd C$ . Associativity of $\symd$ is then then same as showing that $f(A,C)=f(C,A)$ , since $A\symd (B\symd C)= (B\symd C)\symd A = (C\symd B)\symd A$ .

   By expanding $f(A,C)$ , we have \begin{eqnarray*} (A\symd B)\symd C &=& ((A\symd B)-C)\cup (C-(A\symd B)) \\ &=& (((A-B)\cup (B-A))\cap C')\cup (C- ((A\cup B)-(A\cap B))) \\ &=& (((A\cap B')\cup (B\cap A'))\cap C')\cup ((C\cap A\cap B)\cup (C-(A\cup B)) \\ &=& ((A\cap B'\cap C')\cup (B\cap A'\cap C'))\cup ((C\cap A\cap B)\cup (C\cap A'\cap B')) \\ &=& (B\cap A'\cap C')\cup (B\cap A\cap C)\cup (B'\cap A\cap C')\cup (B'\cap A'\cap C). \end{eqnarray*}It is now easy to see that the last expression does not change if one exchanges $A$ and $C$ . Hence, $f(A,C)=f(C,A)$ and this shows that $\symd$ is associative.

Remark. All of the properties of $\symd$ on sets can be generalized to $\symd$ on Boolean algebras.