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

1. 1.

(commutativity of $\triangle$) $A\triangle B=B\triangle A$, because $\cup$ and $\cap$ are commutative.

2. 2.

If $A\subseteq B$, then $A\triangle B=B-A$, because $A\cup B=B$ and $A\cap B=A$.

3. 3.

$A\triangle\varnothing=A$, because $\varnothing\subseteq A$, and $A-\varnothing=A$.

4. 4.

$A\triangle A=\varnothing$, because $A\subseteq A$ and $A-A=\varnothing$.

5. 5.

$A\triangle B=(A-B)\cup(B-A)$ (hence the name symmetric difference).

Proof.

$A\triangle B=(A\cup B)-(A\cap B)=(A\cup B)\cap(A\cap B)^{\prime}=(A\cup B)\cap% (A^{\prime}\cup B^{\prime})=((A\cup B)\cap A^{\prime})\cup((A\cup B)\cap B^{% \prime})=(B\cap A^{\prime})\cup(A\cap B^{\prime})=(B-A)\cup(A-B)$. ∎

6. 6.

$A^{\prime}\triangle B^{\prime}=A\triangle B$, because $A^{\prime}\triangle B^{\prime}=(A^{\prime}-B^{\prime})\cup(B^{\prime}-A^{% \prime})=(A^{\prime}\cap B)\cup(B^{\prime}\cap A)=(B-A)\cap(A-B)=A\triangle B$.

7. 7.

(distributivity of $\cap$ over $\triangle$) $A\cap(B\triangle C)=(A\cap B)\triangle(A\cap C)$.

Proof.

$A\cap(B\triangle 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 (http://planetmath.org/PropertiesOfSetDifference)). This in turns is equal to $((A\cap B)\cup(A\cap C))-((A\cap B)\cap(A\cap C))=(A\cap B)\triangle(A\cap C)$. ∎

8. 8.

(associativity of $\triangle$) $(A\triangle B)\triangle C=A\triangle(B\triangle 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\triangle B)\triangle C$. Associativity of $\triangle$ is then then same as showing that $f(A,C)=f(C,A)$, since $A\triangle(B\triangle C)=(B\triangle C)\triangle A=(C\triangle B)\triangle A$.

By expanding $f(A,C)$, we have

 $\displaystyle(A\triangle B)\triangle C$ $\displaystyle=$ $\displaystyle((A\triangle B)-C)\cup(C-(A\triangle B))$ $\displaystyle=$ $\displaystyle(((A-B)\cup(B-A))\cap C^{\prime})\cup(C-((A\cup B)-(A\cap B)))$ $\displaystyle=$ $\displaystyle(((A\cap B^{\prime})\cup(B\cap A^{\prime}))\cap C^{\prime})\cup((% C\cap A\cap B)\cup(C-(A\cup B))$ $\displaystyle=$ $\displaystyle((A\cap B^{\prime}\cap C^{\prime})\cup(B\cap A^{\prime}\cap C^{% \prime}))\cup((C\cap A\cap B)\cup(C\cap A^{\prime}\cap B^{\prime}))$ $\displaystyle=$ $\displaystyle(B\cap A^{\prime}\cap C^{\prime})\cup(B\cap A\cap C)\cup(B^{% \prime}\cap A\cap C^{\prime})\cup(B^{\prime}\cap A^{\prime}\cap C).$

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 $\triangle$ is associative. ∎

Remark. All of the properties of $\triangle$ on sets can be generalized to $\triangle$ (http://planetmath.org/DerivedBooleanOperations) on Boolean algebras.

Title properties of symmetric difference PropertiesOfSymmetricDifference 2013-03-22 14:36:56 2013-03-22 14:36:56 CWoo (3771) CWoo (3771) 14 CWoo (3771) Derivation msc 03E20