# Is $\complement(A\setminus B)=(\complement A) \setminus (\complement B)$ true or false?

The problem I have is to calculate this term $(\complement A) \setminus (\complement B)$ when I (forexample) let $A=\left \{ a,b,c,d \right \}$ and $B=\left \{ b,c,e,g\right \}$. How do I calculate it? I've tried, but never got the right way to do from this place \begin{equation*} (\complement A)\setminus (\complement B)=\left \{x\in U | x\notin A \right \}\setminus\left \{x\in U | x\notin B \right \} \end{equation*}

I know that $A\setminus B=\left \{ a,d \right \}$, then $\complement(A\setminus B)=\left \{x\in U | x\notin \left \{ a,d \right \} \right \}$.

I’ll get you started. I’m guessing that your $U$ is $\{a,b,c,d,e,f,g\}$; if not, make the appropriate modifications. Start at the easy end:

$$\complement A=\{x\in U:x\notin A\}=\{e,f,g\}\;,$$

since $e,f$, and $g$ are the members of $U$ that are not in $A$. Similarly,

$$\complement(A\setminus B)=\big\{x\in U:x\notin\{a,d\}\big\}=\{b,c,e,f,g\}\;.$$

Can you finish it by calculating $\complement B$ and $\big(\complement A\big)\setminus\big(\complement B\big)$?

• I didn't think about defining $U$ (I forgot it). But if we define this way, is it then true $\complement B=\left \{ a,d,f \right \}$ and $\big(\complement A\big)\setminus\big(\complement B\big)=\left \{ e,g \right \}$? If yes, so we conclude $\complement(A\setminus B)\neq(\complement A) \setminus (\complement B)$? – UnknownW Oct 9 '13 at 3:41
• @AjmalW: Yes, that’s correct. (Any time you’re dealing with complements, you have to keep the universe $U$ in sight.) – Brian M. Scott Oct 9 '13 at 3:48

If the general case is too hard, it might help to look at special or degenerate cases. For example, what does your alleged identity $\complement(A\setminus B)=(\complement A)\setminus(\complement B)$ say if $A=B$? Is it true? Can you prove it?

• Well, i'm not good at proving something. But if we let $A=B$, then $A\setminus B=\varnothing$, $\complement(A\setminus B)=U$ and $(\complement A)\setminus(\complement B)=Ø$, therefore $\complement(A\setminus B)\neq(\complement A)\setminus(\complement B)$. How is it? – UnknownW Oct 9 '13 at 3:46

One way to do this is to calculate which elements $\;x\;$ are in each of the sets. (I'm taking lots of baby steps in what follows, just to make sure the logic is clear. I'm not writing explicitly that $\;x \in U\;$ though.)

For the left hand side, \begin{align} & x \in \complement(A \setminus B) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\complement\;$"} \\ & \lnot(x \in A \setminus B) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$"} \\ & \lnot(x \in A \land \lnot(x \in B)) \\ \equiv & \;\;\;\;\;\text{"logic: simplify using DeMorgan"} \\ & \lnot(x \in A) \lor x \in B \\ \end{align} For the right hand side, \begin{align} & x \in (\complement A) \setminus (\complement B) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$"} \\ & x \in \complement A \land \lnot(x \in \complement B) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\complement\;$, twice"} \\ & \lnot(x \in A) \land \lnot\lnot(x \in B) \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ & \lnot(x \in A) \land x \in B \\ \end{align} So we see that these are not the same: for one the last line has $\;\lor\;$ and for the other it has $\;\land\;$. To see for which $\;A,B\;$ the equation holds, we can equate the above: \begin{align} & \complement(A \setminus B) = (\complement A) \setminus (\complement B) \\ \equiv & \;\;\;\;\;\text{"set extensionality"} \\ & \langle \forall x :: x \in \complement(A \setminus B) \;\equiv\; x \in (\complement A) \setminus (\complement B) \rangle \\ \equiv & \;\;\;\;\;\text{"by the above calculations"} \\ & \langle \forall x :: \lnot(x \in A) \lor x \in B \;\equiv\; \lnot(x \in A) \land x \in B \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify, using (what Dijkstra and Scholten call) the golden rule"} \\ & \langle \forall x :: \lnot(x \in A) \;\equiv\; x \in B \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;\complement\;$"} \\ & \langle \forall x :: x \in \complement A \;\equiv\; x \in B \rangle \\ \equiv & \;\;\;\;\;\text{"set extensionality"} \\ & \complement A = B \\ \end{align} So the equation holds only if $\;A\;$ and $\;B\;$ are each other's complements (w.r.t. $\;U\;$).

That should make it easy to construct a counterexample. (Note that you will have to assume $\;U \not= \varnothing\;$.)