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
$\endgroup$4 Answers
$\begingroup$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.
$\endgroup$ 2 $\begingroup$$\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} $
$\endgroup$ $\begingroup$$(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$$
$\endgroup$ $\begingroup$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.
$\endgroup$ 2
