MHB How Can I Show That the Symmetric Difference of Sets is Associative?

[evinda]

Hello! (Wave)I want to show that $ (A \triangle B) \triangle C=A \triangle (B \triangle C) $.

I have tried the following:

$$ x \in (A \triangle B) \triangle C \Leftrightarrow x \in (A \triangle B)\setminus C \lor x \in C \setminus (A \triangle B) \\ \Leftrightarrow (x \in A \triangle B \wedge x \notin C) \lor (x \in C \wedge x \notin A \triangle B ) \\ \Leftrightarrow (((x \in A \wedge x \notin B) \lor (x \in B \wedge x \notin A)) \wedge x \notin C)\\ \lor (x \in C \wedge (x \in A \cap B \lor x \notin A \cup B) ) \\ \Leftrightarrow ((x \in A \wedge x \notin B \wedge x \notin C) \lor (x \in B \wedge x \notin A \wedge x \notin C)) \lor (x \in C \wedge (x \in A \cap B \lor x \notin A \cup B) ) \\ \Leftrightarrow ((x \in A \wedge x \notin B \cup C) \lor (x \in B \wedge x \notin A \cup C))\lor (x \in C \wedge (x \in A \cap B \lor x \notin A \cup B) ) $$

How could we continue?

 

[Evgeny.Makarov]

If you are patient, it is possible to reduce both sides to a disjunctive normal form, i.e., a disjunction of conjunctions, where every element of a conjunction is $x\in S$ or $x\notin S$ and $S$ is one of $A$, $B$, or $C$. A similar approach is to consider eight cases where $x$ belongs or does not belong to each of $A$, $B$, and $C$, and for each of those cases calculate the truth value of both sides.

If you can rely on the fact that addition is associative in $\mathbb{Z}_2$, then you can notice that $x\in S_1\vartriangle S_2$ iff $\chi_1(x)+\chi_2(x)=1$ where $\chi_i(x)=\begin{cases}1,&x\in S_i\\0,&x\notin S_i\end{cases}$ is the characteristic function of $S_i$. Then
\[
\begin{align}
x\in (A\vartriangle B)\vartriangle C&\iff (\chi_A(x)+\chi_B(x))+\chi_C(x)=1\\
&\iff \chi_A(x)+(\chi_B(x)+\chi_C(x))=1\\&\iff x\in A\vartriangle (B\vartriangle C).
\end{align}
\]

 

[solakis1]

Hello! (Wave)I want to show that $ (A \triangle B) \triangle C=A \triangle (B \triangle C) $.

I have tried the following:

$$ x \in (A \triangle B) \triangle C \Leftrightarrow x \in (A \triangle B)\setminus C \lor x \in C \setminus (A \triangle B) \\ \Leftrightarrow (x \in A \triangle B \wedge x \notin C) \lor (x \in C \wedge x \notin A \triangle B ) \\ \Leftrightarrow (((x \in A \wedge x \notin B) \lor (x \in B \wedge x \notin A)) \wedge x \notin C)\\ \lor (x \in C \wedge (x \in A \cap B \lor x \notin A \cup B) ) \\ \Leftrightarrow ((x \in A \wedge x \notin B \wedge x \notin C) \lor (x \in B \wedge x \notin A \wedge x \notin C)) \lor (x \in C \wedge (x \in A \cap B \lor x \notin A \cup B) ) \\ \Leftrightarrow ((x \in A \wedge x \notin B \cup C) \lor (x \in B \wedge x \notin A \cup C))\lor (x \in C \wedge (x \in A \cap B \lor x \notin A \cup B) ) $$

How could we continue?

$$(x\in A\wedge x\notin B\wedge x\notin C)\vee(x\in B \wedge x\notin A\wedge x\notin C)\vee[x\in C((x\in A\wedge x\in B)\vee(x\notin A\wedge x\notin B))]\Leftrightarrow(x\in A\wedge x\notin B\wedge x\notin C)\vee(x\in B \wedge x\notin A\wedge x\notin C)\vee(x\in C\wedge x\in A\wedge x\in B)\vee(x\in C\wedge x\notin A\wedge x\notin B)$$$$\Leftrightarrow[(x\in A\wedge x\notin B\wedge x\notin C)\vee(x\in C\wedge x\in A\wedge x\in B)]\vee[(x\in B \wedge x\notin A\wedge x\notin C)\vee(x\in C\wedge x\notin A\wedge x\notin B)]\Leftrightarrow [x\in A\wedge (( x\notin B\wedge x\notin C)\vee(x\in C\wedge x\in B))]\vee [x\notin A\wedge ((x\in B \wedge x\notin C)\vee(x\in C\wedge x\notin B))]$$

Can you go on from here??

 

[solakis1]

$$(x\in A\wedge x\notin B\wedge x\notin C)\vee(x\in B \wedge x\notin A\wedge x\notin C)\vee[x\in C((x\in A\wedge x\in B)\vee(x\notin A\wedge x\notin B))]\Leftrightarrow(x\in A\wedge x\notin B\wedge x\notin C)\vee(x\in B \wedge x\notin A\wedge x\notin C)\vee(x\in C\wedge x\in A\wedge x\in B)\vee(x\in C\wedge x\notin A\wedge x\notin B)$$$$\Leftrightarrow[(x\in A\wedge x\notin B\wedge x\notin C)\vee(x\in C\wedge x\in A\wedge x\in B)]\vee[(x\in B \wedge x\notin A\wedge x\notin C)\vee(x\in C\wedge x\notin A\wedge x\notin B)]\Leftrightarrow [x\in A\wedge (( x\notin B\wedge x\notin C)\vee(x\in C\wedge x\in B))]\vee [x\notin A\wedge ((x\in B \wedge x\notin C)\vee(x\in C\wedge x\notin B))]$$

Can you go on from here??

In the above disjunction ,let us calculate each disjunct seperately.
So for :

$$[x\in A\wedge (( x\notin B\wedge x\notin C)\vee(x\in C\wedge x\in B))]$$ we have:

$$[x\in A\wedge (F\vee ( x\notin B\wedge x\notin C)\vee(x\in C\wedge x\in B)\vee F)]$$ (remember we are working in the domain of the algebra of propositions)
$$\Leftrightarrow x\in A\wedge[(x\in B\wedge x\notin B)\vee ( x\notin B\wedge x\notin C))\vee(x\in C\wedge x\in B)\vee (x\in C\wedge x\notin C)] $$

$$\Leftrightarrow x\in A\wedge[((x\in B\wedge x\notin B)\vee ( x\notin B\wedge x\notin C))\vee((x\in C\wedge x\in B)\vee (x\in C\wedge x\notin C))] $$in the $$((x\in B\wedge x\notin B)\vee ( x\notin B\wedge x\notin C))$$

get common factor $$x\notin B$$

in the $$((x\in C\wedge x\in B)\vee (x\in C\wedge x\notin C))$$

get common factor $$x\in C$$ and so we have:

$$\Leftrightarrow x\in A\wedge[x\notin B\wedge(x\in B\vee x\notin C)\vee x\in C\wedge(x\in B\vee x\notin C)]$$

$$\Leftrightarrow x\in A\wedge[(x\notin B\vee x\in C)\wedge (x\in B\vee x\notin C)] $$

And using D.Morgan we have:

$$\Leftrightarrow x\in A\wedge\neg[\neg(x\notin B\vee x\in C)\vee\neg (x\in B\vee x\notin C)] $$

$$\Leftrightarrow x\in A\wedge\neg[(x\in B\wedge x\notin C)\vee (x\notin B\wedge x\in C)] $$

$$\Leftrightarrow x\in A\wedge x\notin (B\triangle C)$$......1

And for the other disjunct $$[x\notin A\wedge ((x\in B \wedge x\notin C)\vee(x\in C\wedge x\notin B))]$$

We have:

$$\Leftrightarrow x\notin A\wedge x\in(B\triangle C)$$........2

And the disjunction of (1) and (2) is:

$$[x\in A\wedge x\notin (B\triangle C)]\vee[ x\notin A\wedge x\in(B\triangle C)]$$

$$\Leftrightarrow A\triangle(B\triangle C)$$