# Element chasing proof

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

-

## 3 Answers

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.

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

-

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

-