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.