# Let A, B, and C be sets. Prove that (A-B) - C = (A-C) - (B-C)

I am utilizing set identities to prove (A-C)-(B-C).

$$\begin{array}{|l}(A−B)− C = \{ x | x \in ((x\in (A \cap \bar{B})) \cap \bar{C}\} \quad \text{Def. of Set Minus} \\ \quad \quad \quad \quad \quad =\{ x | ((x\in A) \wedge (x\in\bar{B})) \wedge (x\in\bar{C})\} \quad \text{Def. of intersection} \\ \quad \quad \quad \quad \quad =\{ x | (A\wedge\overline{C}\wedge\overline{B})\vee(\overline{C}\wedge\overline{B}\wedge C)\} \quad \text{Association Law} \\ \quad \quad \quad \quad \quad =\{ x | ((x\in A) \wedge (x\in\bar{C})) \wedge ((x\in \bar{B}) \wedge (x\in\bar{C}))\} \quad \text{Idempotent Law} \\ \quad \quad \quad \quad \quad =\{ x | (((x\in (A\cap\bar{C})) \cap (x\in (\bar{B} \cap\bar{C})))\} \quad \text{Def. of union} \\ \quad \quad \quad \quad \quad =\{ x | (((x\in (A\cap \bar{C})) \cap \overline{(x\in (B\cup C)))} \} \quad \text{DeMorgan's Law} \\ \quad \quad \quad \quad \quad =\{ x | x \in (A - C) - (B \cup C) \} \quad \text{Def. Set Minus} \\ =(A-C)-(B-C) \end{array}$$

So it looks like I screwed up on the final step. Is there something that I am forgetting to do properly or where am I supposed to go from that final step?

• A comment on line 3: this is not the distribution law. You're using the associative law for intersection, and the idempotent law $\bar C \cap \bar C = \bar C$. Sep 24, 2019 at 17:40
• Also, your expressions like $x \in (x \in A \wedge x\in \bar B) \wedge x \in \bar C$ aren't grammatically correct. You mean $((x \in A) \wedge (x\in \bar B)) \wedge (x \in \bar C)$ etc. Sep 24, 2019 at 17:46
• @MatthewLeingang are those "( )" better now? How would I be using the Associative law for intersectin and then the idempotent law? Sep 25, 2019 at 14:46
• The distributive law is used when you have both $\wedge$ and $\vee$ and you want to distribute one over the other (as with multiplication and addition). You're just swapping parentheses around multiple uses of the same operation. That's the associative law. And the idempotent law allows you to replace $x \in \bar C$ with $(x \in \bar C) \wedge (x \in \bar C)$. Sep 26, 2019 at 9:26
• It's still incorrect to replace $(x \in A) \wedge (x \in \bar C)$ with $(x \in A) \cap (x \in \bar C)$. $\cap$ is an operation on sets, and “$x\in A$” is not a set. You can replace $(x \in A) \wedge (x \in \bar C)$ with $x \in (A \cap \bar C)$. Sep 26, 2019 at 9:30

\begin{align*} (A-C)-(B-C) & = (A\cap\overline{C})-(B\cap\overline{C}) = (A\cap\overline{C})\cap(\overline{B\cap\overline{C})}\\\\ & = (A\cap\overline{C})\cap(\overline{B}\cup C) = (A\cap\overline{C}\cap\overline{B})\cup(\overline{C}\cap\overline{B}\cap C)\\\\ & = A\cap\overline{C}\cap\overline{B} = (A\cap\overline{B})\cap\overline{C} = (A-B)-C \end{align*}

You might also just try to prove this in words. Suppose $$x \in (A-B)-C$$.

• Then $$x \in (A-B)$$ and $$x \notin C$$.
• Since $$x \in (A-B)$$, we know $$x \in A$$ and $$x \notin B$$.
• Since $$x \in A$$ and $$x \notin C$$, we know $$x \in (A-C)$$.
• Since $$x \notin B$$, we know $$x \notin (B-C)$$.
• Since $$x \in (A-C)$$ and $$x \notin (B-C)$$, we know $$x \in ((A-C)-(B-C))$$.

Since this is true for all $$x \in (A-B)-C$$, we know $$(A-B)-C \subseteq ((A-C)-(B-C))$$

Now do it the other way around.

Abbreviating and as $$\land$$ and not as $$\lnot$$,

$$x\in(A-B)-C\iff x\in A-B\land x\notin C \iff x\in A\land x\notin B\land x\notin C\\\iff x\in A\land x\notin C\land\lnot(x\in B\land x\notin C)\iff x\in A-C\land x\notin B-C\\\iff x\in (A-C)-(B-C).$$The third $$\iff$$ uses $$p\land\lnot q\land\lnot r\iff(p\land\lnot r)\land\lnot (q\land\lnot r)$$(you can verify this is a tautology), while the rest use the definition of $$-$$.

• \begin{align*} (A-B)-C & = x\in(A-B)-C \\& = x\in A-B\land x\notin C \quad Def. Set Minus \\& = x\in A\land x\notin B\land x\notin C \quad Def. Set Minus \\& = x\in A\land x\notin C\land\lnot(x\in B\land x\notin C) \quad Distributive Law \\& = x\in A-C\land x\notin B-C \quad Def. Set Minus \\& = x\in (A-C)-(B-C) \quad Def. Set Minus \end{align*} Would these be the proper rules then for your steps? (how do you obtain that Distributive law?) Sep 24, 2019 at 18:25
• @AndrewRyan Most of your manipulations restate a condition on $x$, but $(A-B)-C=x\in(A-B-C)$ is obviously wrong; you should just remove everything to the left of $x$, giving one fewer line. The tautology I used is correct because, given $\lnot r$, $\lnot(q\land\lnot r)=\lnot q\lor r$ is equivalent to $\lnot q$. I'm not sure, however, if "distributive law" or any other specific technical term is used for this useful result.
– J.G.
Sep 24, 2019 at 18:36

All of the above looks like hard math requiring actual thought. I did it by means of an excel spreadsheet. Easy, as there are only 8 possibilities. The two highlighted columns are identical. 