[Math] Some properties of symmetric difference

elementary-set-theory

Definition

For any $A,B$ we define

$$
A\Delta B:=\{x\in A:x\notin B\}\cup\{x\in B:x\notin A\}
$$
and we call it symmetric difference of $A$ and $B$.

Obsertavion

Clearly $A\Delta B\equiv A\setminus B\cup B\setminus A$

Proposizion

The following properties hold

  1. $A\Delta\varnothing=A$
  2. $A\Delta A=A$
  3. $A\cap(B\Delta C)=(A\cap B)\Delta (A\cap C)$
  4. if $A\Delta B=A\Delta C$ then $B=C$
  5. $A\Delta B=B\Delta A$
  6. $(A\Delta B)\Delta C=A\Delta(B\Delta C)$

Proof. Clearly $A\Delta A=A\setminus A\cup\varnothing\setminus A=A\cup\varnothing=A$ and moreover$A\Delta A=A\setminus A\cup A\setminus A=\varnothing\cup\varnothing=\varnothing$ thus we have proved the points $1$ and $2$.

Now previously we observe that for any $X,Y,Z$ it follows that
$$
x\in(X\cap Y)\setminus(Z\cap X)\leftrightarrow x\in X\wedge x\in Y\wedge\{x\notin Z\lor x\notin X\}\leftrightarrow x\in X\wedge x\in Y\wedge x\notin Z\leftrightarrow x\in X\wedge x\notin Y\setminus Z\leftrightarrow x\in X\cap Y\setminus Z
$$
and so we conclude that $X\cap Y\setminus Z=(X\cap Y)\setminus(Z\cap X)$. So it follows that
$$
A\cap(B\Delta C)=A\cap(B\setminus C\cup C\setminus B)=(A\cap B\setminus C)\cup(A\cap C\setminus B)=(A\cap B)\setminus (C\cap A)\cup(A\cap C)\setminus (B\cap A)=(A\cap B)\Delta(A\cap C)
$$
and so we have proved the point $3$.

Now if $A\Delta B=B\Delta A$, that is $A\setminus B\cup B\setminus A=A\setminus C\cup C\setminus A$; and so it follows that
$$
A\setminus B=(A\setminus B\cup B\setminus A)\cap A=(A\Delta B)\cap A=(A\Delta C)\cap A=(A\setminus C\cup C\setminus A)\cap A=A\setminus C
$$
and so
$$
A\cap B=A\setminus(A\setminus B)=A\setminus(A\setminus C)=A\cap C
$$
and then
$$
C\setminus A=(A\setminus C\cup C\setminus A)\setminus A=(A\Delta C)\setminus A=(A\Delta B)\setminus A=(A\setminus B\cup B\setminus A)\setminus A=B\setminus A
$$
and so we conclude that $B=C$, thus we have proved the point 4.
Then though the commutativity of union it easy to see that $A\Delta B=B\Delta A$ and so we have proved $5$.

So as you can see I can't prove the point 6 and so I ask to prove it. Then I ask if I have well proved the point 1 to 5. So could someone help me, please?

Best Answer

I’m inclined to agree with Luke Collins: indicator (or characteristic) functions make this easier. In $(6)$, for instance, I would let $X=A\cup B\cup C$ and define the indicator functions

$$\begin{align*} &\mathbf{1}_A:X\to\{0,1\}:x\mapsto\begin{cases} 1,&\text{if }x\in A\\ 0,&\text{if }x\notin A \end{cases}\\ &\mathbf{1}_B:X\to\{0,1\}:x\mapsto\begin{cases} 1,&\text{if }x\in B\\ 0,&\text{if }x\notin B\ \end{cases}\\ &\mathbf{1}_C:X\to\{0,1\}:x\mapsto\begin{cases} 1,&\text{if }x\in C\\ 0,&\text{if }x\notin C\;. \end{cases} \end{align*}$$

Now verify that $\mathbf{1}_{A\triangle B}=\mathbf{1}_A\oplus\mathbf{1}_B$, where $\oplus$ is pointwise addition modulo $2$:

$$(\mathbf{1}_A\oplus\mathbf{1}_B)(x)=\big(\mathbf{1}_A(x)+\mathbf{1}_B(x)\big)\bmod 2$$

for each $x\in X$. Then for each $x\in X$ you can simply appeal to the associativity of $\oplus$ to argue that

$$\begin{align*} x\in(A\triangle B)\triangle C&\text{ iff }\mathbf{1}_{(A\triangle B)\triangle C}(x)=1\\ &\text{ iff }\mathbf{1}_{A\triangle B}(x)\oplus\mathbf{1}_C(x)=1\\ &\text{ iff }\big(\mathbf{1}_A(x)\oplus\mathbf{1}_B(x)\big)\oplus\mathbf{1}_C(x)=1\\ &\text{ iff }\mathbf{1}_A(x)\oplus\big(\mathbf{1}_B(x)\oplus\mathbf{1}_C(x)\big)=1\\ &\text{ iff }\mathbf{1}_A(x)\oplus\mathbf{1}_{B\triangle C}(x)=1\\ &\text{ iff }\mathbf{1}_{A\triangle(B\triangle C)}(x)=1\\ &\text{ iff }x\in A\triangle(B\triangle C)\;. \end{align*}$$

$(1)$, $(2)$, and $(5)$ also follow easily from properties of $\oplus$: the constant $0$ function is an identity element, each indicator function is its own inverse with respect to $\oplus$, and $\oplus$ is commutative.

Then $(4)$ is immediate from $(1)$, $(2)$, $(5)$, and $(6)$: if $A\triangle B=A\triangle C$, then

$$\begin{align*} B&\overset{(1)}=B\triangle\varnothing\overset{(5)}=\varnothing\triangle B\overset{(2)}=(A\triangle A)\triangle B\overset{(6)}=A\triangle(A\triangle B)\\ &=A\triangle(A\triangle C)\overset{(6)}=(A\triangle A)\triangle C\overset{(2)}=\varnothing\triangle C\overset{(5)}=C\triangle\varnothing\overset{(1)}=C\;. \end{align*}$$

That leaves only $(3)$, which succumbs quickly when you realize that $\mathbf{1}_{A\cap B}=\mathbf{1}_A\otimes\mathbf{1}_B$,where $\otimes$ is pointwise multiplication, which distributes over pointwise addition modulo $2$:

$$(\mathbf{1}_A\otimes\mathbf{1}_B)(x)=\mathbf{1}_A(x)\cdot\mathbf{1}_B(x)\;.$$

For getting a better intuitive grasp of the symmetric difference I agree with Greg Martin: it’s useful to know (and follows easily from the indicator function approach) that the members of a symmetric difference of a finite family of sets are the things that are in an odd number of those sets.

Related Question