Associativity of symmetric set difference

by user356478   Last Updated October 09, 2019 17:20 PM

The symmetric difference $A$ △ $B$ of $A$ and $B$ is defined as $(A - B) \cup (B - A)$. (The set of elements that belong to A or B but not both.)

(a) Construct a truth table to show that △ is associative.

(b) Show that $x$ belongs to $A$ △ $(B$ △ $C)$ if and only if $x$ belongs to an odd number of the sets $A$, $B$ and $C$ and use this observation to give a second proof that △ is associative.

For part (a), I'd be grateful is someone could post the full truth table, as I'm not entirely sure what column headings they are looking for.

For part (b), this is what I did:

(For the left to right implication) Let $x \in$ $A$ △ $(B$ △ $C)$. Then, by the definition of △, we have either $x \in$ $A$ or $x \in$ $(B$ △ $C)$ but not both. So if $x \in A$ then either it is not in $B$ nor $C$ or it is in both $B$ and $C$. So here $x$ can be in just $A$, or in $A, B$ and $C$. If $x \in (B$ △ $C)$, then $x \notin A$. So by a similar logic $x$ can be in $B$ or $C$, but not both. The implication works both ways, hence the 'iff'.

However, I'm not sure how this proves associativity. I tried to write it as

$A$ △ $(B$ △ $C)$ = ($A$ △ $B$) $\cap$ ($A$ △ $C$) $\cap$ ($B$ △ $C$) $\cup$ $(A\cap B\cap C)$ And then associativity would follow by swapping $A$ and $C$ but I'm not sure if this is the right way of doing it.

Tags :

Here is a truth table with an intermediate column;

$$\ \begin{array}{|ccc|c|c|} \hline A&B&C&A\Delta B&(A\Delta B)\Delta C\\ \hline 0&0&0&0&0\\ 0&0&1&0&1\\ 0&1&0&1&1\\ 0&1&1&1&0\\ 1&0&0&1&1\\ 1&0&1&1&0\\ 1&1&0&0&0\\ 1&1&1&0&1\\ \hline \end{array}$$

Here is a proof:

$$\left(A\triangle B\right)\triangle C=\left(A\cup B\cup C\right)\cap\left(A\cup B^{c}\cup C^{c}\right)\cap(A^{c}\cup B\cup C^{c})\cap(A^{c}\cup B^{c}\cup C)=(B\cup C\cup A)\cap(B\cup C^{c}\cup A^{c})\cap(B^{c}\cup C\cup A^{c})\cap(B^{c}\cup C^{c}\cup A)=(B\bigtriangleup C)\bigtriangleup A=A\bigtriangleup(B\bigtriangleup C)$$

The proof of symmetric difference operator associativity comes from late professor David Meredith home page: http://online.sfsu.edu/meredith/Exploration_and_Proof/divided_difference.pdf

practically one page paper contains prepositions and eventually proof of associativity. Proof assume that operator $$\triangle$$ is commutative as proven below from preposition 7:

$$A\triangle B=(A\cup B)\cap(A^{c}\cup B^{c})=(B\cup A)\cap(B^{c}\cup A^{c})=B\triangle A$$

Hope it helps.

Related Questions

Updated March 11, 2018 10:20 AM

Updated July 02, 2015 13:08 PM

Updated March 22, 2017 00:20 AM

Updated February 01, 2018 22:20 PM

Updated February 22, 2017 09:20 AM