2
$\begingroup$

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$
  • $\begingroup$ The 3rd equality is false. You can't just drop the parenthesis. $\endgroup$ – azarel Sep 15 '13 at 1:02
  • $\begingroup$ 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? $\endgroup$ – user94908 Sep 15 '13 at 1:12
1
$\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$
2
$\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$

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.