# How to prove that $A\cap B\subseteq C$ and $A^c\cap B\subseteq C$ imply that $B\subseteq C$?

How do you solve this problem??

Suppose that $A\cap B\subseteq C$, and $A^c\cap B\subseteq C$. Prove that $B$ is a subset of $C$.

I don't know where even to begin

Can anyone help?

Thank you

-
Do you mean $(A\cap B)^C \subseteq C$, or that $A^C \subseteq C$ and $B^C \subseteq C$? – amWhy May 22 '13 at 18:14
@amWhy: I think the OP means that $A^c\cap B\subseteq C$. – Asaf Karagila May 22 '13 at 18:25
i meant to say A∩B ⊆ C and A^C ∩ B ⊆ C. Prove that B ⊆ C. – amie May 22 '13 at 18:45

Hint:

Pick an element $b\in B$. If it's in $A$, conclude that it's in $C$, and if it isn't in $A$, it's in the complement of $A$ -- conclude that it is in $C$.

Those are the two options, so we covered all of them.

Work closely with the definitions, and you'll be fine.

-
@amie - Asaf has given you good advice. Definitions are crucial to mathematics. To write $B \subseteq C$ means something. Whenever a student tells me I don't even know how to begin, I give then the advice Asaf has just given you: what are you trying to show; what does that mean. I'm not trying to pick on you, I want you to always keep Asaf's advice with you. It will serve you in good stead as you go on to encounter other proofs. – Chris Leary May 22 '13 at 20:51

Note from the venn diagram $B=(A\cap B)\cup(A^c\cap B)$. You are given
$A\cap B\subseteq C$
$A^c\cap B\subseteq C$.
If you take the union both sides (you can do that), we have
$(A\cap B)\cup(A^c\cap B)\subseteq C \cup C$ which implies $B\subseteq C$

-

Venn says:

The upper case is for $A \subseteq C$ while the lower case is for $A \nsubseteq C$.

It is evident that the region $B$ is enclosed in $C$ $(B\subseteq C)$ if and only if both the yellow and the green regions are enclosed in $C$.

We have

\begin{align} (A \cap B \subseteq C) \land (A^c\cap B\subseteq C) &\implies ((A \cap B) \cup (A^c\cap B))\subseteq C \\&\implies ((A \cup A^c)\cap B)\subseteq C \\&\implies (U \cap B) \subseteq C \\&\implies B \subseteq C. \end{align}

Where $U$ is the universal set.

-
This diagram hints that $A\subseteq C$. This need not be the case. And this is exactly why working with Venn diagrams can be confusing for the general case. – Asaf Karagila May 22 '13 at 19:16
$C$ is arbitrary. As long as it encloses the regions shown the condition holds. – Maazul May 22 '13 at 19:19
Yes. I know that $C$ is arbitrary. But the diagram doesn't show that. It shows that $A\cup B\subseteq C$. – Asaf Karagila May 22 '13 at 19:20
Edited to include the case $A \nsubseteq C$. – Maazul May 22 '13 at 19:28
So, how do you prove it in words? i understand by looking at the graphs but im having difficulty writing it down as in words. thank you – amie May 22 '13 at 19:43

You could also think of it another way: What if $B \nsubseteq C$? Then you have several possibilities:

$(A \subseteq C) \land (A^C \nsubseteq C) \implies A^C\cap B\nsubseteq C \\ (A \nsubseteq C) \land (A^C \subseteq C) \implies A\cap B\nsubseteq C \\ (A \nsubseteq C) \land (A^C \nsubseteq C) \implies (A\cap B\nsubseteq C) \land (A^C\cap B\nsubseteq C) \\ (A \subseteq C) \land (A^C \subseteq C) \implies C = U \implies B \subseteq C$

Regardless, all these cases would contradict the original (given) statements, or, as in the last case, the assumption that $B \nsubseteq C$.

EDIT: Last two cases added, and previous cases edited, after @Asaf Karagila pointed out the incompleteness/incorrectness of my answer.

-
And what if neither $A$ nor $A^c$ are subsets of $C$? What if $C$ is the universal set and in fact both $A$ and $A^c$ are subsets of $C$? – Asaf Karagila May 22 '13 at 23:25
Well, then, (respectively) both givens would be contradicted or $B \subseteq C$ anyway, which would contradict this temporary assumption of $B \nsubseteq C$ above. – luolimao May 23 '13 at 1:40
If, for example, $B\subseteq A$ then even in the case $A^c\nsubseteq C$ we still have $A^c\cap B\subseteq C$. – Asaf Karagila May 23 '13 at 1:53
Derp, should I just tack on "$\lor B \subseteq C$" to the end of the first 3 cases or give up now and delete this answer? – luolimao May 23 '13 at 1:58