0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – UnknownW Oct 9 '13 at 3:41
  • $\begingroup$ @AjmalW: Yes, that’s correct. (Any time you’re dealing with complements, you have to keep the universe $U$ in sight.) $\endgroup$ – Brian M. Scott Oct 9 '13 at 3:48
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – UnknownW Oct 9 '13 at 3:46
1
$\begingroup$

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\;$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.