4
$\begingroup$

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$

  • 0
    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.2012-10-28

4 Answers 4

2

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.

6

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

4

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.

  • 1
    This is great as a general technique. Thnx :) Not directly, but it provides a way out of any sticky situation as my was.2012-10-28
3

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.