A, B, and C are subsets of a universal set U.
Prove $(A-C) \cap B \neq \emptyset \to A \cap B \not\subseteq C$.
I figured the best way to prove that is the contrapositive, I got this far:
Contrapositive: $A \cap B \subseteq C \to (A-C) \cap B = \emptyset$
$\forall x \in U, x \in A \land x \in B \to x \in C$.
Now I'm stuck, and I'm not sure how to go from there. I can see that I need to show that A-C is removing all elements in the intersection, but I can't figure out how I can do that from the conditional.
I tried just proving it directly, without the contrapositive, but that didn't work either, there I didn't even know how to start.
Any help would be awesome!
Best Answer
Contrapositive is probably a good idea. Assume $A\cap B\subseteq C$ and prove $(A-C)\cap B=\emptyset$ by contradiction.
Suppose $x\in(A-C)\cap B$, then $x\in A-C$ and $x\in B$. So $x\in A$ and $x\not\in C$.
Since $x\in A$ and $x\in B$ we have $x\in A\cap B$.
Since $A\cap B\subseteq C$ we have $x\in C$.
But we already have $x\not\in C$, so this is a contradiction. Therefore $(A-C)\cap B=\emptyset$.
Direct proof is actually also quite easy.
Assume $(A-C)\cap B$ is not empty, then it contains an element $x$.
This means $x\in A$ and $x\not\in C$ and $x\in B$.
Therefore $x\in A\cap B$ and $x\not\in C$, so $A\cap B$ is not a subset of $C$.