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\}$.
$\endgroup$ 22 Answers
$\begingroup$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.
$\endgroup$ $\begingroup$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*}$$
and for your example
$$\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*}$$
$\endgroup$
