4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @nbro He defined $\Delta$ as the diagonal intersection in line 2. $\endgroup$ Nov 17, 2016 at 20:04
  • $\begingroup$ 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. $\endgroup$ Nov 18, 2016 at 0:44

3 Answers 3

9
$\begingroup$

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)}.$$

$\endgroup$
7
  • $\begingroup$ 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$ $\endgroup$ Nov 18, 2016 at 12:14
  • $\begingroup$ You want $x\in A\Delta B \iff \chi_{A\Delta B}(x) = 1$. $\endgroup$
    – mvw
    Nov 18, 2016 at 12:21
  • $\begingroup$ @mvw And why is that happening. Sorry but I can't understand $\endgroup$ Nov 18, 2016 at 12:25
  • $\begingroup$ 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$. $\endgroup$
    – alans
    Nov 18, 2016 at 12:26
  • $\begingroup$ 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$ $\endgroup$ Nov 18, 2016 at 13:44
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Nov 18, 2016 at 12:20
  • $\begingroup$ 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. $\endgroup$ Nov 18, 2016 at 18:21
  • $\begingroup$ 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. $\endgroup$ Nov 19, 2016 at 9:52
  • $\begingroup$ @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. $\endgroup$
    – user5826
    Jun 9, 2019 at 19:54
1
$\begingroup$

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*} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .