Proving $A\setminus(B\setminus C)$ is not equal to $(A\setminus B)\setminus C$ I have several of these types of problems, and it would be great if I can get some help on one so I have a guide on how I can solve these.
The question is: 

Prove $A \setminus (B\setminus C) \neq  (A\setminus B) \setminus C$

I know I must prove both sides are not equivalent to each other to complete this proof.
Here's my shot:
We start with left side.


*

*if $x$ is in $A$, then $x$ is not in $B$, not not in $C$

*so $x$ is in $A$ and $C$

*if $x$ is in $A$, then it's not in $B$ $\rightarrow$ $(A\setminus B)$

*but if $x$ is in $A\setminus B$, then it must not be in $C$

*however, earlier we stated $x$ is in both $A$ and $C$

*we see that the two sides are not equal


Is this the right idea?  Should I then reverse the proof to prove it the other way around, or is that unnecessary?  Should it be more formal?
Thanks!
 A: $(\varnothing \setminus \varnothing) \setminus \varnothing = \varnothing \setminus ( \varnothing \setminus \varnothing)$, so you can't prove that they are not equal.  However, you CAN find a counterexample that violates the propositiong $ A \setminus (B \setminus C) = (A \setminus  B) \setminus C$.
For example, set $A = B = C = \{1\}$  Then, the left side of the equality is equal to $\{1\}$, but the right side is equal to $\varnothing$.
A: In order to show that equality does not always hold, you should produce specific examples of $A$, $B$ and $C$ where the two sides do not agree.
Note that the left-hand side is equivalent to
$$\begin{align*}
A\setminus (B\setminus C) &= A\setminus (B\cap C^c)\\
&= A\cap (B\cap C^c)^c\\
&= A\cap (B^c\cup C).
\end{align*}$$
That is, the things that are in $A$ and either in $C$ or not in $B$.
On the other hand, the right hand side is equivalen to:
$$\begin{align*}
(A\setminus B)\setminus C &= (A\cap B^c)\setminus C\\
&= (A\cap B^c)\cap C^c\\
&= A\cap B^c\cap C^c
\end{align*}$$
that is, the things that are in $A$, and not in $B$, and not in $C$.
So an easy way to find examples is to find one in which there is an element that is in both $A$ and $C$; then it will be on the left-hand side but not on the right-hand side.
So take $A=\{1\}$, $B=\varnothing$, $C=\{1\}$. Then 
$$A\setminus(B\setminus C) = \{1\}\setminus(\varnothing\setminus \{1\}) = \{1\}\setminus\varnothing = \{1\},$$
but
$$(A\setminus B)\setminus C = (\{1\}\setminus\varnothing)\setminus\{1\} = \{1\}\setminus\{1\} = \varnothing.$$
This proves that equality does not always hold.
Note that there are cases where the two expressions are equal; for example, if $C$ is empty. More generally, if $A$ is disjoint from $C$, then $A\subseteq C^c$, so $(A\setminus B)\setminus C = A\setminus B$, and 
$$A\setminus (B\setminus C) = A\cap (B^c\cup C) = (A\cap B^c)\cup (A\cap C) = A\cap B^c$$
so the two are equal. This is the only situation where you have equality: if $x\in A\cap C$, then $x\in A\setminus(B\setminus C)$, but $x\notin $A\cap B^c\cap C^c=(A\setminus B)\setminus C$. 
A: To find an example to show that $A\setminus(B\setminus C)$ is not necessarily equal to $(A\setminus B)\setminus C$, think like this.
Look at $A\setminus(B\setminus C)$. If $B=C$, we will be taking away nothing from $A$. But (most of the time) $(A\setminus B)\setminus C$ takes something away from $A$.
Now for details. Let $A=\{1,2\}$, $B=C=\{2\}$. Then $B\setminus C$ (everything in $B$ which is not in $C$) is the empty set. So $A\setminus(B\setminus C)=\{1,2\}$.
But $A\setminus B=\{1\}$, and therefore $(A\setminus B)\setminus C=\{1\}.$
A: Alternatively, as a more general solution, you can calculate for which sets the equality holds:
\begin{align}
& A \setminus(B \setminus C) \;=\; (A \setminus B) \setminus C \\
\equiv & \;\;\;\;\;\text{"set extensionality"} \\
& \langle \forall x :: x \in A\setminus(B \setminus C) \;\equiv\; x \in (A \setminus B) \setminus C \rangle \\
\equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$, two times"} \\
& \langle \forall x :: x \in A \land \lnot(x \in B \setminus C) \;\equiv\; x \in (A \setminus B) \land \lnot(x \in C) \rangle \\
\equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$, two more times"} \\
& \langle \forall x :: x \in A \land \lnot(x \in B \land \lnot(x \in C)) \;\equiv\; (x \in A \land \lnot(x \in B)) \land \lnot(x \in C) \rangle \\
\equiv & \;\;\;\;\;\text{"logic: use DeMorgan; simplify"} \\
& \langle \forall x :: x \in A \land (x \not\in B \lor x \in C) \;\equiv\; x \in A \land x \not\in B \land x \not\in C \rangle \\
\equiv & \;\;\;\;\;\text{"logic: extract common part from both sides of $\;\equiv\;$"} \\
& \langle \forall x :: x \in A \Rightarrow (x \not\in B \lor x \in C \;\equiv\; x \not\in B \land x \not\in C) \rangle \\
\equiv & \;\;\;\;\;\text{"logic: simplify: $\;P \lor Q \equiv P \land \lnot Q\;$ is equivalent to $\;\lnot Q\;$"} \\
& \langle \forall x :: x \in A \Rightarrow x \not\in C \rangle \\
\equiv & \;\;\;\;\;\text{"logic: rewrite $\;\Rightarrow\;$ -- so that we can go back to set notation"} \\
& \langle \forall x :: \lnot(x \in A \land x \in C) \rangle \\
\equiv & \;\;\;\;\;\text{"introduce $\;\cap\;$ and $\;\emptyset\;$ using their definitions"} \\
& A \cap C = \emptyset \\
\end{align}
So any sets $\;A\;$ and $\;C\;$ which have at least one element in common are a counterexample.
