next up previous contents
Next: The cartesian product of Up: Operations with sets Previous: Difference   Contents


Symmetric difference

Definition 3.2.29   Let $ A$ and $ B$ be any two sets. The symmetric difference of $ A$ and $ B$ is the set denoted by $ A \Delta B$ and who consists of all the elements that belong to exactly one of the sets $ A$ and $ B$, and not to both, i.e.

$\displaystyle A \Delta B = (A \cup B) \setminus (A \cap B).$    

Figure 16: Symmetric difference of two sets.
\begin{figure}
\centering
\mbox{\epsfig{file=SymmetricDifference.eps, height=4cm}}
\end{figure}

We can rewrite the definition a follows:

$\displaystyle A \Delta B = \{ x \; \vert \; x \in A$    (exclusive) or $\displaystyle x \in B \}$    

Proposition 3.2.30   Let $ A$ and $ B$ be any two sets. Then

$\displaystyle A \Delta B = (A \setminus B) \cup (B \setminus A).$    

Proposition 3.2.31 (the commutative law)   Let $ A$ and $ B$ be two sets. Then the following equality holds:

$\displaystyle A \Delta B = B \Delta A.$    

Proposition 3.2.32 (the associative law)   Let $ A$,$ B$and $ C$ be three sets. Then the following equality holds:

$\displaystyle A \Delta (B \Delta C )= (A \Delta B )\Delta C.$    

Figure 17: A double symmetric difference.
\begin{figure}
\centering
\mbox{\epsfig{file=SymmDiffAssoc.eps,height=4.5cm}}
\end{figure}

Proof. We can write down a proof using truth tables; as this is exactly the proof of the associative law of the ``exclusive or'' from Chapter 2, we are done. Anyway, we wish at least to outline a proof using properties of operations on sets. On the one hand, we have: (the reader will fill the missing rows):

$\displaystyle A \Delta (B \Delta C )$ $\displaystyle = [A \cap ( B \cap C^C)^C]\cup [A^C \cap (B
 \cap C^C)]$    
$\displaystyle \quad$ $\displaystyle = [A \cap (B^C \cup C)]\cup [ A^C \cap B \cap
 C^C]$    
$\displaystyle \quad$ $\displaystyle = \dots$    
$\displaystyle \quad$ $\displaystyle = (A \cap B^C \cap C^C ) \cup (A^C
 \cap B \cap C^C ) \cup (A^C \cap B^C \cap C ) \cup(A \cap B \cap C ).$    

On the other hand, we have:

$\displaystyle (A \Delta B) \Delta C$ $\displaystyle = [(A \cap B^C)\cap C^C] \cup [(A \cap
 B^C)^C\cap C]$    
$\displaystyle \quad$ $\displaystyle = [ A \cap B^C \cap C^C] \cup [ (A^C \cup B)
 \cap C ]$    
$\displaystyle \quad$ $\displaystyle = \dots$    
$\displaystyle \quad$ $\displaystyle = (A \cap B^C \cap C^C ) \cup (A^C
 \cap B \cap C^C ) \cup (A^C \cap B^C \cap C ) \cup(A \cap B \cap C ).$    

Whence the required equality. $ \qedsymbol$

A much more simple proof can be written, using characteristic functions (v.i. prop associativity of symmetric difference 2).
next up previous contents
Next: The cartesian product of Up: Operations with sets Previous: Difference   Contents
root 2002-06-10