Tell me more ×
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:

(1)(A\C)\(B\C) = (A\B)\C 

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

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

For RHS, since $a∈A$, we have that $a ∈ (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

3 Answers

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

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.