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.

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

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

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

$A\triangle A=\varnothing$ , because $A\subseteq A$ and $A-A=\varnothing$ .
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.

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

(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)$ . ∎

(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
Canonical name	PropertiesOfSymmetricDifference
Date of creation	2013-03-22 14:36:56
Last modified on	2013-03-22 14:36:56
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	14
Author	CWoo (3771)
Entry type	Derivation
Classification	msc 03E20