Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
I double checked it and it's OK. –  LavaScornedOven Oct 28 '12 at 21:23
1  
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

4 Answers 4

up vote 3 down vote accepted

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.

share|improve this answer
    
This technique proves all true algebraic set identities. –  sperners lemma Oct 28 '12 at 22:39
1  
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$.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.