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.

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

Figure 16: Symmetric difference of two sets.

We can rewrite the definition a follows:

$$A \Delta B = \{ x \; \vert \; x \in A x \in B \}$$

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

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

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

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

Figure 17: A double symmetric difference.

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):

$$A \Delta (B \Delta C ) = [A \cap ( B \cap C^C)^C]\cup [A^C \cap (B \cap C^C)]$$

$$\quad = [A \cap (B^C \cup C)]\cup [ A^C \cap B \cap C^C]$$

$$\quad = \dots$$

$$\quad = (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:

$$(A \Delta B) \Delta C = [(A \cap B^C)\cap C^C] \cup [(A \cap B^C)^C\cap C]$$

$$\quad = [ A \cap B^C \cap C^C] \cup [ (A^C \cup B) \cap C ]$$

$$\quad = \dots$$

$$\quad = (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).