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 would like to construct a formal proof of the following:

$$(A\setminus C)\setminus(B\setminus C) = (A\setminus B)\setminus C$$

Let $a∈A$ be an arbitrary element, we will show that $a\in A \cap \overline B \cap \overline C$.

For LHS, since $a\in A$, we have that $a\in (A \cap \overline C) \cap (\overline B \cap \overline C)$. This is equivalent to $a\in (A \cap \overline B) \cap \overline C$.

For RHS, since $a\in A$, we have that $a\in (A \cap \overline B) \cap \overline C$

$\therefore lhs \equiv rhs$ and this concludes the proof

I would be grateful for any feed back on this element chasing proof. Is it flawed or where should improvements be made?

Thanks

share|improve this question

4 Answers 4

up vote 1 down vote accepted

You’re in trouble already in the first line of your argument:

Let $a\in A$ be an arbitrary element, we well show that $a\in A\cap\overline B\cap\overline C$.

You can’t show this, because it’s not necessarily true that an arbitrary element of $A$ belongs to $\overline B\cap\overline C$. It also isn’t what you want to show. At this point you’re trying to show that $$(A\setminus C)\setminus(B\setminus C)\subseteq(A\setminus B)\setminus C\;,\tag{1}$$ so you should be starting with an arbitrary $a\in(A\setminus C)\setminus(B\setminus C)$, like this:

Let $a\in(A\setminus C)\setminus(B\setminus C)$ be arbitrary. Then $a\in A\setminus C$, and $a\notin B\setminus C$. Since $a\in A\setminus C$, $a\in A$ and $a\notin C$. Since $a\notin B\setminus C$, either $a\notin B$, or $a\in C$. But we know that $a\notin C$, so it must be the case that $a\notin B$. Putting the pieces together, we see that $a\in A$ and $a\notin B$, so $a\in A\setminus B$, and moreover $a\notin C$, so $a\in(A\setminus B)\setminus C$. This proves $(1)$.

To complete the proof you must show that

$$(A\setminus B)\setminus C\subseteq(A\setminus C)\setminus(B\setminus C)\tag{2}\;,$$

so this time you should start with an arbitrary element of $(A\setminus B)\setminus C$:

Let $a\in(A\setminus B)\setminus C$ be arbitrary. Then $a\in A\setminus B$, and $a\notin C$. Since $a\in A\setminus B$, $a\in A$, and $a\notin B$. We now know that $a\in A$ and $a\notin C$, so $a\in A\setminus C$. We also know that $a\notin B$, so $a\notin B\setminus C$, and therefore $a\in(A\setminus C)\setminus(B\setminus C)$. This proves $(2)$, and $(1)$ and $(2)$ together yield the desired result that $(A\setminus C)\setminus(B\setminus C)=(A\setminus B)\setminus C$.

There’s nothing tricky about any of this: it’s all just using the definition of set difference. It’s an example of what I call a follow-your-nose proof: you do the most straightforward, natural thing at each step, and it works.

share|improve this answer
    
Thanks for the great feedback. This will serve as a very helpful template to all of us on math.stackexchange trying to improve our 'proof' building –  bosra Nov 18 '12 at 19:04
    
@bosra: You’re very welcome. –  Brian M. Scott Nov 18 '12 at 19:05

$(A-C)=A\cap C'$ and $(B-C)=B\cap C'$ then $$(A-C)-(B-C)=(A\cap C')\cap(B\cap C')'=\\(A\cap C')\cap(B'\cup C)=(A\cap C'\cap B')\cup(A\cap C'\cap C)$$ but $(A\cap C'\cap C)=\emptyset$ so $$(A-B)-(B-C)=(A\cap C'\cap B')=A\cap(B\cup C)'=A-(B\cup C)$$ or $$(A-B)-(B-C)=(A\cap B'\cap C')=(A\cap B')\cap C'=(A-B)- C$$

share|improve this answer

$\rm\begin{eqnarray} {\bf Hint}\quad (A\backslash C)\backslash (B\backslash C) &\:=\: &\rm A\cap C'\cap\, (B\cap C')'\\ &=&\rm A\cap C'\cap (B'\cup C)\\ &=&\rm A\cap (C'\cap B'\cup C'\cap C) \\ &=&\rm (A\cap B')\cap C'\\ &=&\rm (A\backslash B)\backslash C \end{eqnarray} $

share|improve this answer

My favorite version of element chasing is to start at the most complex side, expand the definitions to get to the element/logic level, then simplify, and finally go back to the set level.

In this case, for every $\;x\;$, \begin{align} & x \in (A \setminus C) \setminus (B \setminus C) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$"} \\ & x \in A \setminus C \;\land\; \lnot (x \in B \setminus C) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$, twice"} \\ & x \in A \;\land\; \lnot (x \in C) \;\land\; \lnot (x \in B \land \lnot (x \in C)) \\ \equiv & \;\;\;\;\;\text{"logic: simplify by using $\;\lnot (x \in C)\;$ on other side of $\;\land\;$"} \\ & x \in A \;\land\; \lnot (x \in C) \;\land\; \lnot (x \in B \land \text{true}) \\ \equiv & \;\;\;\;\;\text{"logic: simplify; rearrange -- to better match the other side"} \\ & x \in A \;\land\; \lnot (x \in B) \;\land\; \lnot (x \in C) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$"} \\ & x \in A \setminus B \;\land\; \lnot (x \in C) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$"} \\ & x \in (A \setminus B) \setminus C \\ \end{align} By set extensionality, this proves the original statement.

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.