2
$\begingroup$

The problem statement is in the title.

I'm proving a problem in class and it's necessary for me to show the above containment. I've drawn some Venn diagrams to make sure the containment actually makes sense and it does, yet I'm having trouble proving this rigorously.

I know that to begin, we'd let $x\in A\Delta B$ and eventually show that $x\in A\Delta C\cup B\Delta C$. Since $x\in A\Delta B$, $x\in A\setminus B$ or $x\in B\setminus A$. Yet, I don't know how to show $x$ would end up in $C$.

Also, the proof of this requires proving an "or" statement, that is, showing that $x\in A\Delta C$ or $x\in B\Delta C$. Would supposing $x\notin B\Delta C$ or $x\notin A\Delta C$ help to prove this?

Thanks for any help or feedback!

$\endgroup$
  • $\begingroup$ I am most certain that I answered this question before. $\endgroup$ – Asaf Karagila Jan 11 '14 at 7:22
3
$\begingroup$

Cases?

Take $\;x\in A\Delta B=(A\cup B)\setminus (A\cap B)\;$ , and suppose $\;x\in A\;$ (and thus $\;x\notin B\;$, of course).

Case 1: If $\;x\in C\;$ then:

$$(i)\;\;x\in A\cap C\implies x\notin B\cap C\implies x\in B\Delta C$$

$$(ii)\;\;x\notin A\cap C\implies \ldots $$

Continue on.

$\endgroup$
  • $\begingroup$ Thanks for the response. Would your $(ii)$ written be Case 2 for $x\notin C$? $\endgroup$ – Shant Danielian Jan 11 '14 at 3:01
  • $\begingroup$ I'm not sure what you tried to ask @ShantDanielian, but my (ii) above is the second case of $\;x\in C\;$ . $\endgroup$ – DonAntonio Jan 11 '14 at 3:32
  • $\begingroup$ What I'm confused about is if we're supposing that $x\in A$ and the case we're in is also $x\in C$, how can $x$ not be in $A\cap C$? $\endgroup$ – Shant Danielian Jan 11 '14 at 7:50
  • $\begingroup$ ...and so case (ii) is not relevant, @ShantDanielian...:) Now, case 2: $\;x\notin C\;$...what can you say about it? $\endgroup$ – DonAntonio Jan 11 '14 at 10:10
  • $\begingroup$ Ah guess I should of concluded that. What I got for the second part was if $x\notin C$ then $x\notin A\cap C$ and $x\notin B\cap C$, which means that $x\in A\cup C$ and so $x\in A\Delta C$. $\endgroup$ – Shant Danielian Jan 11 '14 at 20:37
1
$\begingroup$

Whenever you want to prove an "or" statement, assume one of the "or"'s is false. In this case, try assuming that $x\notin B\Delta C$, and then prove that $x\in A\Delta C$.

Here's why this works:

Let $A$ and $B$ be some statements. Consider the statement "(not $A$) implies $B$". This is false exactly when $B$ is false and $A$ is false. In other words, it has the same truth table as "$A$ or $B$". Thus, proving "$A$ or $B$" is the same as proving "(not $A$) implies $B$".

$\endgroup$
0
$\begingroup$

Another way to approach, notice $A\Delta B = (A\cup B)-(A\cap B)$

HINT: Let $x\in A\Delta B$

$\implies x\in A\cup B \land x\notin A\cap B$

$\implies x\in A\cup B \land x\in (A\cap B)^C$

$\implies x\in A\cup B\cup C \land x\in (A\cap B)^C \cup C^C$

Remember $x\in A \implies x\in A\cup B$ for whatever set $B$

$\endgroup$
  • $\begingroup$ How is $x\in A\cup B$ and not in $A\cup B$? Did you mean $A\cap B$? $\endgroup$ – Shant Danielian Jan 11 '14 at 3:13
  • $\begingroup$ Sorry, typo. Editing $\endgroup$ – AndreGSalazar Jan 11 '14 at 3:14
  • $\begingroup$ @AndrewGSM, by de Morgan Laws, we have that $$x\notin A\cap B\iff x\in (A\cap B)^c=A^c\cup B^c$$ and not what you wrote. $\endgroup$ – DonAntonio Jan 11 '14 at 3:37
  • $\begingroup$ Your implication in the line before the last one doesn't look justified. Would you mind? $\endgroup$ – DonAntonio Jan 11 '14 at 3:45
  • $\begingroup$ Yes, edited again. The first time Shant told me I only edited the first thing I saw wrong, didn't read the whole answer again. Pardon me, I think it is now correct $\endgroup$ – AndreGSalazar Jan 11 '14 at 3:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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