Element chasing proof that $(A\setminus C)\setminus(B\setminus C) = (A\setminus B)\setminus C$

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

Solution 1:

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.

Solution 2:

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