# What does the negation of set difference give?

I was given the following problem:

For sets A, B, C, and D. Prove or disprove that $(A-B)-(C-D) = (A-C)-(B-D)$.

My proof by counterexample was:

Let $A=\{1,2\}, B=\{2,3\}, C=\{3,5\}, D=\{2,4\}$. Then, $(A-B)-(C-D) = \{1\}$, but $(A-C)-(B-D) = \{1,2\}$. Thus, the statement is false.

But if I try to use the definition of set difference $A-B = \{x \in A \wedge x \notin B\}$. Something goes wrong.

$(A-B)-(C-D)=\{(x \in A \wedge x \notin B) \wedge \neg(x \in C \wedge x\notin D)\} = \{(x \in A \wedge x \notin B) \wedge (x \notin C \vee x\in D)\} = \{x \in A \wedge x \notin B \wedge x \notin C \vee x\in D\} = \{1,2,4\}$.

• The 3rd equality is false. You can't just drop the parenthesis. – azarel Sep 15 '13 at 1:02
• Okay, but, if I use associativity and commutativity to change the order and parentheses, am not still able to arrive to the set $\{(x\in A \vee x\in D) \wedge (x\notin B \wedge x\notin C)\}$, which gives the same result? – user94908 Sep 15 '13 at 1:12

You’re badly misusing the equals sign in that last computation. $(A\setminus B)\setminus(C\setminus D)$ is most definitely not equal to

$$\{(x\in A\land x\notin B)\land\neg(x\in C\land x\notin D)\}\;:$$

the latter is a set with one element, and that element is the statement

$$(x\in A\land x\notin B)\land\neg(x\in C\land x\notin D)\;.$$

What you mean, I expect, is that $x\in(A\setminus B)\setminus(C\setminus D)$ if and only if

$$(x\in A\land x\notin B)\land\neg(x\in C\land x\notin D)\;,$$

which is true. Using $\leftrightarrow$ for if and only if, we can write

\begin{align*} x\in(A\setminus B)\setminus(C\setminus D)&\leftrightarrow (x\in A\land x\notin B)\land\neg(x\in C\land x\notin D)\\ &\leftrightarrow x\in A\land x\notin B\land(x\notin C\lor x\in D)\;, \end{align*}

but the last expression is not logically equivalent to

$$x\in A\land x\notin B\land x\notin C\lor x\in D\;;$$

that’s the same kind of mistake as writing $a\cdot b\cdot(c+d)=a\cdot b\cdot c+d$.

If you want to continue the calculation, by getting rid of the last set of parenthesis, you need to use the distributive law $p\land(q\lor r)\leftrightarrow (p\land q)\lor(p\land r)$, though the most straightforward continuation doesn’t give you anything very nice:

\begin{align*} x\in(A\setminus B)\setminus(C\setminus D)&\leftrightarrow (x\in A\land x\notin B)\land\neg(x\in C\land x\notin D)\\ &\leftrightarrow x\in A\land x\notin B\land(x\notin C\lor x\in D)\\ &\leftrightarrow (x\in A\land x\notin B\land x\notin C)\lor(x\in A\land x\notin B\land x\in D)\\ &\leftrightarrow\Big(x\in A\land\neg(x\in B\lor x\in C)\Big)\lor\\ &\qquad\Big(x\in(A\land x\in D)\land x\notin B\Big)\\ &\leftrightarrow(x\in A\land x\notin B\cup C)\lor(x\in A\cap D)\land x\notin B)\\ &\leftrightarrow x\in\big(A\setminus(B\cup C)\big)\lor x\in(A\cap D)\setminus B\\ &\leftrightarrow x\in\big(A\setminus(B\cup C)\big)\cup\big((A\cap D)\setminus B\big)\;, \end{align*}

\begin{align*} \big(A\setminus(B\cup C)\big)\cup\big((A\cap D)\setminus B\big)&=\big(\{1,2\}\setminus\{2,3,5\}\big)\cup\big(\{2\}\setminus\{2,3\}\big)\\ &=\{1\}\setminus\varnothing\\ &=\{1\}\;. \end{align*}
One way also to prove or disprove the statement $(A-B)-(C-D)=(A-C)-(B-D)$ for sets A, B, C and D is showing that $(A-B)-(C-D)\subset(A-C)-(B-D)$ and $(A-C)-(B-D)\subset(A-B)-(C-D)$. If you can show that they are subsets of each other, then they are equal. But if one is not a subset of the other, then we can say that they are not equal.