# Proving $(A \triangle B)\cup C = (A\cup C)\triangle (B\setminus C)$ using set algebra

I tried to prove this equation $(A\bigtriangleup B)\cup C=(A\cup C)\bigtriangleup(B\setminus C)$ by elementhood and set algebra but with no result. I can see that equality stands in Venn's diagrams, and I also proved it with truth tables, but I would like to have solution with set algebra or elementhood. I would appreciate any pointers in solving this.

This is from Velleman's How to Prove It, chapter 1 section 4 exercise 13.

Solution with set algebra

After some time pounding this exercise, I came up with following solution:

$$(A\bigtriangleup B)\cup C=(A\cup C)\bigtriangleup(B\setminus C)\\ =((A\cup C)\cap (B\cap C^C)^C)\cup((B\cap C^C)\cap(A\cup C)^C)\\ =((A\cup C)\cap (B^C\cup C))\cup(B\cap C^C\cap A^C)\\ =(C\cup(A\cap B^C))\cup(B\cap C^C\cap A^C)\\ =C\cup(A\cap B^C)\cup(B\cap A^C)\\ =(A\bigtriangleup B)\cup C$$

-
I double checked it and it's OK. –  LavaScornedOven Oct 28 '12 at 21:23
How do your tries go? If everything else fails, you should be able to adapt a truth table proof by systematically rewriting each side to a union of terms such as $A\cap\overline B\cap C$. –  Henning Makholm Oct 28 '12 at 21:24
With elementhood I decomposed both sides and tried to connect them, but that didn't work. I just couldn't recombine statements. With set algebra I didn't get too far, so not worth mentioning. –  LavaScornedOven Oct 28 '12 at 21:27

Here is a good way to prove it by decomposing the sets into venn diagram

• $A \cup D \cup G \cup E$
• $B \cup D \cup G \cup F$
• $C \cup F \cup G \cup E$

Write out the equation in full

$$((A \cup D \cup G \cup E)\bigtriangleup(B \cup D \cup G \cup F))\cup (C \cup F \cup G \cup E) = ((A \cup D \cup G \cup E)\cup (C \cup F \cup G \cup E))\bigtriangleup(B \cup D \cup G \cup F\setminus (C \cup F \cup G \cup E))$$

now we just compute both sides until we prove equality

$$(A \cup B \cup G \cup E \cup F)\cup (C \cup F \cup G \cup E) = (A \cup C \cup D \cup G \cup E \cup F)\bigtriangleup(B \cup D \cup G \cup F\setminus (C \cup F \cup G \cup E))$$

$$A \cup B \cup C \cup G \cup E \cup F = (A \cup C \cup D \cup G \cup E \cup F)\bigtriangleup(B \cup D)$$

$$A \cup B \cup C \cup G \cup E \cup F = A \cup B \cup C \cup G \cup E \cup F$$

and since any 3 sets can be decomposed like this this proves it for all sets.

-
This technique proves all true algebraic set identities. –  sperners lemma Oct 28 '12 at 22:39
This is great as a general technique. Thnx :) Not directly, but it provides a way out of any sticky situation as my was. –  LavaScornedOven Oct 28 '12 at 23:11

Let $x\in (A\bigtriangleup B)\cup C$. Then $x\in (A\bigtriangleup B)\setminus C$ or $x\in C$. In the first case, $x\in A$ and $x\not\in B$ (so $x\in A\cup C$ and $x\not\in B\setminus C$) or $x\not\in A$ and $x\in B$ and $x\not\in C$ (so $x\not\in A\cup C$ and $x\in B\setminus C$). In the second case, $x\in A\cup C$ and $x\not\in B\setminus C$.

Let $x\in (A\cup C)\bigtriangleup(B\setminus C)$. We want to show that if $x\not\in C$ then $x\in A\bigtriangleup B$. Now either $x\in A$ or $x\not\in A$. In the first case, $x\in A\cup C$ so $x\not\in B\setminus C$ so $x\not\in B$. In the second case, we have $x\not\in A\cup C$ so $x\in B\setminus C$ so $x\in B$.

-

We can show mutual set inclusion. If $x\in (A \triangle B)\cup C$ then $x\in A\triangle B$ or $x\in C$.

If $x\in C$ then $x\in A\cup C$ and $x\notin B\setminus C$ so that $x\in (A\cup C)\triangle (B\setminus C)$.

Suppose then that $x\notin C$. Then $x\in A$ or $x\in B$ but $x\notin A\cap B$.

If $x\in A,\ x\notin B$ then $x\in A\cup B$ and $x\notin B\setminus C$ so $x\in (A\cup C)\triangle (B\setminus C)$.

If $x\in B,\ x\notin A$ then $x\in B\setminus C$ and $x\notin A\cup C$ so $x\in (A\cup C)\triangle (B\setminus C)$.

The above shows $(A \triangle B)\cup C\subseteq (A\cup C)\triangle (B\setminus C)$.

For the other direction, suppose $x\in(A\cup C)\triangle (B\setminus C)$:

If $x\in C$ then $x\in (A\triangle B) \cup C$.

If $x\notin C$ then either $x\in A\cup C \implies x\in A$ and $x\notin B\setminus C \implies x\notin B$ or $x \in B\setminus C \implies x\in B$ and $x\notin A\cup C \implies x\notin A$.

In either case, we have $x\in (A\triangle B) \implies x\in (A\triangle B)\cup C$.

This shows mutual set inclusion.

-

Here is an alternative (and late) answer which uses elementhood, i.e., we first translate from set theory to logic, and then reason in the logic domain.

We will use the following definition of $\Delta$: for every $A$, $B$, and $x$ $$(0) \;\; x \in A \Delta B \;\equiv\; x \in A \not\equiv x \in B$$ We will also use the following rule of logic: $$(1) \;\; P \not\equiv Q \;\equiv\; \lnot P \equiv Q$$

Starting on the left hand side of the original equation, for all $x$ we have \begin{align*} & x \in (A \Delta B) \cup C \\ \equiv & \;\;\;\;\;\text{"expand definitions of \cup and \Delta"} \\ & (x \in A \not\equiv x \in B) \lor x \in C \\ \equiv & \;\;\;\;\;\text{"logic, to prepare for next step: change \lor to \Rightarrow; (1)"} \\ & x \notin C \Rightarrow (x \notin A \equiv x \in B) \\ \equiv & \;\;\;\;\;\text{"logic: distribute antecedent of \Rightarrow over \equiv"} \\ (*) \;\;\;\; & x \notin A \land x \notin C \equiv x \in B \land x \notin C \\ \end{align*}

Similarly, for the right hand side, for all $x$ we calculate

\begin{align*} & x \in (A \cup C) \Delta (B \setminus C) \\ \equiv & \;\;\;\;\;\text{"expand definitions of \Delta, \cup, and \setminus"} \\ & x \in A \lor x \in C \not\equiv x \in B \land x \notin C \\ \equiv & \;\;\;\;\;\text{"logic: (1); distribute \lnot over \lor"} \\ (*) \;\;\;\; & x \notin A \land x \notin C \equiv x \in B \land x \notin C \\ \end{align*}

Since formulae $(*)$ are identical, by extensionality this proves the original equation.

-