# 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!

-
I'm assuming that by \ you meant \setminus (the relative complement). Also, the statement is not true for any $A$, $B$, and $C$; for example, if $B=C=\varnothing$, and $A$ is any set, then we do in fact have that $$A\setminus(B\setminus C)=(A\setminus B)\setminus C.$$ Please see here for how to typeset common math expressions with LaTeX, and see here for how to use Markdown formatting. – Zev Chonoles Jul 18 '12 at 6:16
Yes, thank you for editing it for me. I'm a bit confused by your statement....would you kindly explain? – pauliwago Jul 18 '12 at 6:20
@pauliwago In putting the slashes \ did you mean set difference or something else? – Andrew Salmon Jul 18 '12 at 6:21
@pauliwago: As Andrew Salmon has also said below, the claim that $$A\setminus (B\setminus C)\neq (A\setminus B)\setminus C$$ for any sets $A$, $B$, and $C$ is false; that is, there are some choices for $A$, $B$, and $C$ for which it is instead the case that $$A\setminus (B\setminus C)\;\;\fbox{=\strut}\;\;(A\setminus B)\setminus C$$ – Zev Chonoles Jul 18 '12 at 6:22
The claim may or may not be true. When that happens you are note supposed to prove anything but look for a counterexample instead, i.e. examples of sets $A,B,C$ such that the equality does not hold. The claim you are supposed to refute that $A\setminus(B\setminus)$ is ALWAYS the same as $(A\setminus B)\setminus C$. – Jyrki Lahtonen Jul 18 '12 at 6:37

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$. - Thanks for your answer. What does that small C indicate? – pauliwago Jul 18 '12 at 6:41 It indicates the complement of a set. – Andrew Salmon Jul 18 '12 at 7:47$(\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$. - I see your reasoning here. So I guess this proof is invalid... – pauliwago Jul 18 '12 at 6:28 @pauliwago: The approach is wrong. To show that the two sets are not necessarily equal (there are cases where they are!) you have to exhibit a specific instance in which they are not equal. That is, you need a counterexample to the equality, not a proof that they are never equal (because it is false that they are never equal). – Arturo Magidin Jul 18 '12 at 6:32 Actually you don't even have to use a specific set (your$\{1\}$). Just$A=B=C$suffices. Then$(A\setminus A)\setminus A=\emptyset$but$A\setminus(A\setminus A)=A$. Indeed, even$A=C$is sufficient, so specifying$B$isn't needed either. – celtschk Jul 18 '12 at 13:59 @ArturoMagidin: He did give a counterexample. First he gave a counterexample to$A\setminus(B\setminus C)\neq(A\setminus B)\setminus C$, then he gave a counterexample to$A\setminus(B\setminus C)=(A\setminus B)\setminus C$. – celtschk Jul 18 '12 at 14:03 @celtschk: Andrew did. The original poster, pauliwago, did not. I understood the comment pauliwago made here to refer to his own "proof" in the original post, not to Andrew Salmon's examples here. – Arturo Magidin Jul 18 '12 at 16:04 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\}.- 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.

-