3
$\begingroup$

Prove that: $A\cap (B-C) = (A\cap B)-(A\cap C)$.

Tried to prove this by using Algebra of Classes. Then used idempotent property in $A$ as well as double negation in $A$ but still it didn't work.

  • 0
    The proof of this type of equality is usually as follows: take an element in the lhs and show it's in the rhs, and vice versa.2012-07-17

3 Answers 3

1

If an element is in the left side, then it is:

  1. in A
  2. in B
  3. not in C

If an element is in the right side, then it is

  1. in $A\cap B$
  2. not in $A\cap C$

which is the same thing as saying "it's in A and B, but not in C". To fully justify:

An element on the left is in A and B, meaning that it's in the $A\cap B$ on the right. It's not in C though, which excludes it from the $A\cap C$ on the right. Those together mean that it's in the right-hand side. So if it's in the left, it's in the right. In other words,

$A\cap(B-C)\subseteq (A\cap B)-(A\cap C)$

Can we run this process in reverse? Yes! If an element is in the righthand side, it's in $A\cap B$, so it's in $A$ and in $B$. However it's not in $A\cap C$. If it's in $A$ (as we've determined) but not in $A\cap C$, it must not be in $C$. If it's not in $C$ in the first place, but it's in $B$, then it must still be in $B-C$. It's also in $A$, so it must be in $A\cap (B-C)$ as well. In other words,

$A\cap(B-C)\supseteq (A\cap B)-(A\cap C)$

These two taken together imply that both sets are equal.

3

Note that: $\begin{align*} (A\cap B)-(A\cap C) &= (A\cap B)\cap (A\cap C)^c&&\text{(definition of complement)}\\ &=(A\cap B)\cap(A^c\cup C^c) &&\text{(De Morgan)}\\ &= ((A\cap B)\cap A^c)\cup ((A\cap B)\cap C^c)&&\text{(distributivity of }\cap\text{ over }\cup\text{)}\\ &= (A\cap A^c\cap B) \cup (A\cap B\cap C^c)&&\text{(assoc. and comm. of }\cap\text{)}\\ &= \varnothing \cup (A\cap B\cap C^c)&&(A\cap A^c=\varnothing)\\ &= A\cap B\cap C^c&&\text{(}\varnothing\text{ is an identity for }\cup\text{)}\\ &= A\cap (B\cap C^c)&&\text{(associativity of }\cap\text{)}\\ &= A\cap (B-C).&&\text{(definition of complement)} \end{align*}$

You can do this by double inclusion, of course, but since you said you were trying to do it by using algebra of classes, I think the above is what you were going for; it amounts to the logical equivalence $P\land(Q\land \neg R) \equiv (P\land Q)\land \neg(P\land R).$

  • 0
    Very much said. Thanks!2012-07-17
2

You take an element on one side and prove that it is also an element on the other side.

One way: Let $x \in A \cap (B \setminus C)$. Then clearly $x\in A\cap B$. Can you see why $x$ is not in $C$? If so then $x \in (A\cap B)\setminus (A\cap C)$

The other way: Let $x \in (A\cap B)\setminus (A\cap C)$. Then clearly $x\in A$. Is it also in $B\setminus C$?