# Prove that if $\ B - C \subseteq A^{c}$ then $\ A \cap B \subseteq C$.

Question:

Prove that if $\ B - C \subseteq A^{c}$ then $\ A \cap B \subseteq C$.

My attempt:

I think proof by contradiction would be the easiest.

Assume $\ B - C \subseteq A^{c}$ and $\ A \cap B \nsubseteq C$.

Then,

$x \in A \cap B \implies x \in A \cap B \text{ and } x\notin C$

I am stuck here. How do I show a contradiction?

Note that $A\cap B\nsubseteq C$ does not mean any element of $A \cap B$ is not in $C$, and thus your direction is not correct.

To show the proof:

$\forall x \in A \cap B$, we know $x\in A$ and $x \in B$. Since $x \in A$, we know $x \notin B \setminus C$ (because $\ B - C \subseteq A^{c}$).

However, meanwhile $x \in B$, so it has be to that $x \in C$ (because otherwise $x \in B \setminus C$, contradiction). Thus we are done.

• So $\ x\notin B - C \implies x \in C$ ? – user444945 Aug 13 '17 at 5:25
• It is from $x \notin B \setminus C$ and $x \in B$ that we conclude $x \in C$. Think that given $x \in B$ and now if $x \notin C$, then $x \in B \setminus C$ - but we know that $x \notin B \setminus C$, thus it has to be that $x \in C$. – Yujie Zha Aug 13 '17 at 5:26

A direct proof may be easier:

Since $B - C = B \cap C^c \subseteq A^c$, it follows that $$A = (A^c)^c \subseteq (B \cap C^c)^c = B^c \cup C.$$ Therefore, $$A \cap B \subseteq (B^c \cup C) \cap B = B \cap C \subseteq C.$$

• How can I prove it by using containment? – user444945 Aug 13 '17 at 5:14
• You may proceed as the other answer does. – Zhanxiong Aug 13 '17 at 5:19
• $\ A \cap B \nsubseteq C$. Then, "There exist some x such that $x \in A \cap B \implies x \in A \cap B \ and \ x\notin C$ not for all x. – Pranita Gupta Aug 13 '17 at 5:19

Indeed assume $B - C \subseteq A^c$. We want to show $A \cap B \subseteq C$. Assuming the opposite we have some $x \in A \cap B$ with $x \notin C$. OK so far.

Go on with: $x \in B$ and $x \notin C$ so $x \in B - C$. Now the base assumption $B-C \subseteq A^c$ gives us that $x \in A^c$, so $x \notin A$. This contradicts $x \in A \cap B$. This contradiction proves the inclusion.

• So If $A \cap B \nsubseteq C$ then if $\ x \in A \cap B \implies x \notin C$ right? – user444945 Aug 13 '17 at 5:51
• @JoshMitkitzel no, we only know there exists at least one such element. It need not hold for all elements as you claim. – Henno Brandsma Aug 13 '17 at 6:09