# Prove that two sets are the same

I need to prove that $(A \Delta B ) \Delta C = A \Delta (B\Delta C)$for any sets A,B,C, and $A \Delta B = (A-B)\cup(B-A)$.

I tried to expand both the left hand side and the right hand side expression, and after that my expresion was composed only of sample proposition ($x \in A / x\in B/x\in C\ x\notin A\ x\notin B$ or $x \notin C$) and then prove that using a truth table. My problem is that the truth table does not get me that the expression is a tautology.

• @nbro He defined $\Delta$ as the diagonal intersection in line 2. Nov 17, 2016 at 20:04
• I think drawing the Venn diagram is the best way to understand why this is true. Your instructor might or might not accept that as a proof. Nov 18, 2016 at 0:44

I think it is the easiest way to prove it by using characteristic functions:

Since $$\chi_{A \Delta B}=\chi_A+\chi_B\mod 2,$$ we have: $$\chi_{(A \Delta B)\Delta C}=\chi_{(A \Delta B)}+\chi_C\mod 2=(\chi_A+\chi_B)+\chi_C\mod 2=\chi_A+(\chi_B+\chi_C)\mod 2=\chi_A+\chi_{B \Delta C}\mod 2=\chi_{A \Delta (B\Delta C)}.$$

• My instructor used this method with characteristic functions too. I need two more things to understand your proof. First I will need a proof for why $\chi_{A \Delta B}=\chi_A+\chi_B\mod 2$. And second in the last equality $\chi_{(A \Delta B)}+\chi_C\mod 2=(\chi_A+\chi_B)+\chi_C\mod 2$ shouldn't be $\chi_{(A \Delta B)}+\chi_C\mod 2=((\chi_A+\chi_B)mod 2+\chi_C)mod 2$ Nov 18, 2016 at 12:14
• You want $x\in A\Delta B \iff \chi_{A\Delta B}(x) = 1$.
– mvw
Nov 18, 2016 at 12:21
• @mvw And why is that happening. Sorry but I can't understand Nov 18, 2016 at 12:25
• It is ok. Addition mod 2 is associative, because of that equality holds. You have to check four cases ($x\in A\cap B$, $x\in A\setminus B$, $x\in B\setminus A$, $x\notin A\cup B$) to prove that $\chi_{A \Delta B}=\chi_A+\chi_B\mod 2$ holds. Also, you have to know definition of characteristic function: $\chi_{A}(x)=1$ for $x\in A$ and $\chi_{A}(x)=0$ for $x\notin A$. Nov 18, 2016 at 12:26
• Yeah now I see why the equality holds but I'm still not abel to prove that $\chi_{A \Delta B}=\chi_A+\chi_B\mod 2$. What I did is to prove that $\chi_{A \Delta B}=\chi_A+\chi_B + 2\chi_A \chi_B$ Nov 18, 2016 at 13:44

By definition $$x\in A\bigtriangleup B\iff (x\in A \land x\notin B) \lor(x\in B \land x\notin A)\tag1$$ $$x\in B\bigtriangleup C\iff (x\in B \land x\notin C) \lor(x\in C \land x\notin B)\tag2$$ Hence \begin{align} x\notin A\bigtriangleup B&\iff (x\notin A \lor x\in B) \land (x\notin B \lor x\in A) \\ &\iff (x\notin A \land x\notin B) \lor (x\notin A \land x\in A) \\ &\quad\quad\quad\lor (x\in B \land x\notin B) \lor (x\in B \land x\in A) \\ &\iff (x\notin A \land x\notin B) \lor (x\in B \land x\in A)\tag3 \end{align} And \begin{align} x\notin B\bigtriangleup C&\iff (x\notin B \lor x\in C) \land (x\notin C \lor x\in B) \\ &\iff (x\notin B \land x\notin C) \lor (x\notin B \land x\in B) \\ &\quad\quad\quad\lor (x\in C \land x\notin C) \lor (x\in C \land x\in B) \\ &\iff (x\notin B \land x\notin C) \lor (x\in C \land x\in B)\tag4 \end{align} Thus \begin{align} x\in (A\bigtriangleup B)\bigtriangleup C &\iff (x\in A\bigtriangleup B \land x\notin C) \lor (x\in C \land x\notin A\bigtriangleup B) \\ &\iff (((x\in A \land x\notin B) \lor(x\in B \land x\notin A))\land x\notin C) \\ &\quad\quad\quad\lor (x\in C \land ((x\notin A \land x\notin B) \lor (x\in B \land x\in A)))\tag{by (1),(3)} \\ &\iff (x\in A \land x\notin B \land x\notin C) \lor (x\notin A \land x\in B \land x\notin C) \\ &\quad\quad\quad\lor (x\notin A \land x\notin B \land x\in C) \lor (x\in A \land x\in B \land x\in C)\tag5 \end{align} And \begin{align} x\in A\bigtriangleup (B\bigtriangleup C) &\iff (x\in A \land x\notin B\bigtriangleup C) \lor (x\notin A \land x\in B\bigtriangleup C) \\ &\iff ((x\in A \land ((x\notin B \land x\notin C) \lor (x\in B \land x\in C))) \\ &\quad\quad\quad\lor (x\notin A \land ((x\in B \land x\notin C) \lor(x\in C \land x\notin B)))\tag{by (2),(4)} \\ &\iff (x\in A \land x\notin B \land x\notin C) \lor (x\in A \land x\in B \land x\in C) \\ &\quad\quad\quad\lor (x\notin A \land x\in B \land x\notin C) \lor (x\notin A \land x\notin B \land x\in C)\tag6 \end{align} By $$(5)$$ and $$(6)$$ $$x\in (A\bigtriangleup B)\bigtriangleup C\iff x\in A\bigtriangleup (B\bigtriangleup C)$$ Hence $$(A\bigtriangleup B)\bigtriangleup C=A\bigtriangleup (B\bigtriangleup C)$$

• Your method was my first attempt to solve this. At that time my instructor told me that this method is not good because it is a thing of intuition and is not a formal proof. For example this $(x\notin A \lor x\in B) \land$ $(x\notin B \lor x\in A)$ $\iff (x\notin A \land x\notin B) \lor (x\notin A \land x\in A)$ might be clear for you, but it may not be clear for other persons because of the lack of their intuition. At least that told me my instructor, even thought I find this method a good way to solve this. Nov 18, 2016 at 12:20
• The formula you pointed out uses De Morgan's law, which should be known by everyone learning logic. This is the standard way of proof but complicated though. Nov 18, 2016 at 18:21
• Yeah, I know this was a bad example. My point (or my instructor's point) here is that this method uses a lot of intuition and I should give a more formal solution. Nov 19, 2016 at 9:52
• @RaducuMihai How does this answer use intuition? It is purely formal. This is how a computer would say to do it. There is no intuition here. Jun 9, 2019 at 19:54

A variation of hermes's proof.

For any subsets $$A, B, C$$ of a given set $$X.$$ By notation, $$A^c = X\setminus A.$$

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

In particular, $$\Delta$$ is commutative.

\begin{align*} &(A\Delta B)\Delta C\\ =\;&\{[(A\cup B)\cap (A\cap B)^c]\cup C\}\cap[(A\cup B)\cap (A\cap B)^c\cap C]^c\\ =\;&(A\cup B\cup C)\cap(A^c\cup B^c\cup C)\cap[(A^c\cap B^c)\cup (A\cap B)\cup C^c]\\ =\;&(A\cup B\cup C)\cap(A^c\cup B^c\cup C)\cap\{[(A^c\cup B)\cap (B^c\cup A)]\cup C^c\}\\ =\;&(A\cup B\cup C)\cap(A^c\cup B^c\cup C)\cap(A^c\cup B\cup C^c)\cap (B^c\cup A\cup C^c) \end{align*} Then, doing permutation $$A\mapsto C, B\mapsto B, C\mapsto A$$ to get \begin{align*} &A\Delta (B\Delta C)\\ =\;&(C\Delta B)\Delta A\\ =\;&(C\cup B\cup A)\cap (C^c\cup B^c\cup A)\cap (C^c\cup B\cup A^c)\cap (B^c\cup C\cup A^c)\\ =\;&(A\Delta B)\Delta C \end{align*}