# How does one prove (A - B) - C ⊆ (A - C) - (B - C)

When proving this I'm not sure how to 'take out' the C on the RHS of the equation.

The LHS is

(x ∈ A) ∧ !(x ∈ B) ∧ !(x ∈ C)

The RHS is

(x ∈ A) ∧ !(x ∈ C) ∧ !(x ∈ B) ∧ !(x ∈ C)

How does how prove LHS is a subset of RHS?

-
Take an element in the LHS and prove it must be in the RHS. – Patrick Li Jan 29 '13 at 6:34

Just show that each $x\in(A\setminus B)\setminus C$ belongs to $(A\setminus C)\setminus(B\setminus C)$.

Suppose that $x\in(A\setminus B)\setminus C$; then $x\in A\setminus B$, and $x\notin C$. Since $x\in A\setminus B$, we know further that $x\in A$ and $x\notin B$.

Now put the pieces back together. First, $x\in A$ and $x\notin C$, so $x\in A\setminus C$. Moreover, $x\notin B$, so certainly $x\notin B\setminus C$, since $B\setminus C$ is a subset of $B$. But that means that $x\in A\setminus C$ and $x\notin B\setminus C$, which is exactly what’s required to say that $x\in(A\setminus C)\setminus(B\setminus C)$.

Since $x$ was an arbitrary element of $(A\setminus B)\setminus C$, this shows that every element of $(A\setminus B)\setminus C$ belongs to $(A\setminus C)\setminus(B\setminus C)$ and hence that $(A\setminus B)\setminus C\subseteq(A\setminus C)\setminus(B\setminus C)$.

(I call this approach element-chasing. It’s one of the most straightforward ways to prove that one set is a subset of another.)

-

Note that according to set theory Theorems, we have $A-B=A\cap B'$ where in $B'$ is a complement of $B$ recpect to our universal set $U$. So we have then:

$$D=(A-B)-C=(A\cap B')\cap C'$$ so if $x\in D$ then $x\in A\cap B'$ and $x\in C'$ then $x\in A, x\in B', x\in C'$ so $$x\in A,x\in C'\longrightarrow x\in(A-C)\\x\in B', x\in C\longrightarrow x\in B',x\notin C\longrightarrow x\in(B'\cup C)\longrightarrow x\in(B\cap C')'$$ therfore $x\in(A-C)$ and $x\in(B\cap C')'$ which leads us to $$x\in(A-C)\cap (B\cap C')'$$. THis is wht you are looking for.

-
Nicely done, Babak! +1 – amWhy Jan 29 '13 at 15:57
@amWhy: :-) ... – Babak S. Jan 29 '13 at 19:23

Note that $(A\setminus C)\setminus (B\setminus C)$ is obtained by removing from $A\setminus C$ the part that is in $B\setminus C$. So we are removing a set that is a subset of $B$. It follows that $(A\setminus C)\setminus (B\setminus C)\subseteq (A\setminus C)\setminus B$.

But $(A\setminus C)\setminus B= (A\setminus B)\setminus C$, since each is obtained by removing from $A$ the part of $A$ that is in $B$ or $C$.

-

The LHS is as you have written

$$x \in A \land x \notin B \land x \notin C \tag{1}.$$

However, your RHS is wrong, it should be $$x \in A \land x \notin C \land \neg (x \in B \land x \notin C)$$ which is equivalent to $$x \in A \land x \notin C \land (x \notin B \lor x \in C).$$ Still, if you look closely, then you can see that we have $x \notin C$ there, so $(x \notin B \lor x \in C)$ simplifies to $x \notin B$. Finally we have

$$x \in A \land x \notin C \land x \notin B \tag{2}$$

which is the same as (1) because commutativity of conjunction. Note that we in fact proved equality

$$(A-B)-C = (A-C)-(B-C).$$

I hope this helps ;-)

-