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

Solutions Collecting From Web of "Proving $(A \triangle B)\cup C = (A\cup C)\triangle (B\setminus C)$ using set algebra"

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

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.

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.