For two sets we define $A \Delta B = (A \cup B) \setminus (A \cap B)$ (symmetric difference).

Problem: Proof that \begin{align*} A \Delta C \subset (A \Delta B) \cup (B \Delta C). \end{align*}

Attempt at proof: Let $x \in A \Delta C$. Then $x \in (A \cup C)$ and $x \notin (A \cap C)$. Thus $x \in A$ or $x \in C$. When $x \in A$, then also $x \in A \cup B$. When $x \in C$, then also $x \in B \cup C$.

Now, I don't know how to proceed. I'm not sure how to use the fact that $x \notin (A \cap C)$ in my proof.

  • $\begingroup$ Do you mean $\subseteq$? $\endgroup$ – simonzack Aug 6 '15 at 9:30
  • $\begingroup$ No, I mean a proper subset. $\endgroup$ – Kamil Aug 6 '15 at 9:32
  • 1
    $\begingroup$ If $B=\varnothing$, and $A\cap C=\varnothing$, then you get equality. $\endgroup$ – Asaf Karagila Aug 6 '15 at 9:35
  • $\begingroup$ What would be an example such that the equality does not hold? What would I have to choose $A, B$ and $C$ as? $\endgroup$ – Kamil Aug 6 '15 at 9:56

Suppose that $x\in A$, what would cause it not to be in the RHS set? If $x\notin A\mathbin{\triangle} B$ and $x\notin B\mathbin{\triangle} C$.

Since we already assumed that $x\in A$, then for $x\notin A\mathbin{\triangle}B$, it would have to be the case that $x\in B$ as well. But then in order for $x$ not to be an element of $B\mathbin{\triangle}C$, it means that $x\in C$ as well. So $x\in A\cap C$. But since $x\notin A\cap C$, this cannot be the case.

An alternative method, would be to simply note that:

$$A\mathbin{\triangle}C=(A\mathbin{\triangle}B)\mathbin{\triangle}(B\mathbin{\triangle}C)=\bigl((A\mathbin{\triangle}B)\cup (B\mathbin{\triangle}C)\bigr)\setminus\bigl((A\mathbin{\triangle}B)\cap (B\mathbin{\triangle} C)\bigr)\subseteq\ldots$$

But this only works after you've proved that $\mathbin{\triangle}$ is associative, of course.

  • $\begingroup$ I understand that $x \in B$ would have to be the case. But then what you say after that, i.e. that in order for $x$ not to be an element of $B \Delta C$, why do we need $x \in C$ for that? $\endgroup$ – Kamil Aug 6 '15 at 9:33
  • $\begingroup$ Because it's already an element of $B$. So it is in $B\cup C$, but it is not an element of $B\mathbin{triangle}C$, so it is necessarily the case that $x\in C$ as well. $\endgroup$ – Asaf Karagila Aug 6 '15 at 9:34
  • $\begingroup$ I see. So what is your proof technique here? Did you derive a contradiction? What is the conclusion? $\endgroup$ – Kamil Aug 6 '15 at 9:38
  • $\begingroup$ The conclusion is that if $x\in A$, and $x$ is not in the RHS, then $x\in C$. Therefore $x\notin A\mathbin{\triangle} C$. So it's a contrapositive proof. $\endgroup$ – Asaf Karagila Aug 6 '15 at 9:42

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.