# With $A,B,C \subseteq X$ prove that $(A \cap B) \subseteq C$ if and only if $A \subseteq ((X \setminus B) \cup C$)

I drew a Venn diagram and it is clear to me why it is true. However I just have difficulty formalizing the proof. So far I first tried proving from left to right, assuming that $(A \cap B) \subseteq C$ and working from there to try and show that $A \subseteq ((X \setminus B) \cup C)$, but I'm completely stuck. Any help would be appreciated.

• Perhaps trying to come up with how you would say $A \subseteq ((X - B) \cup C)$ would help: For each $a \in A$, I would say $a \in X - B$ means that "$a$ is not in $B$", while $a \in C$ of course means "$a$ is in $C$". We're linking them with a union, so we want to say that the first is true, or, the second is true... – pjs36 Feb 1 '17 at 15:53

I would have a look at the definitions of subset, complement, intersection and union.

Let $x \in A$. Then if $x \in B$, we have by $A \cap B \subseteq C$ that $x \in C$ and thus $x \in (X \setminus B) \cup C$. If $x \notin B$, we have that $x \in X \setminus B$ and thus again $x \in (X \setminus B) \cup C$. Conversly, if $x \in A \cap B$, then $x \in A$ and thus $x \in (X\setminus B) \cup C$. But $x \in X\setminus B$ cannot be true since if $x \in A \cap B$ so is $x \in B$ hence $x \in C$.

With the use of De Morgan's Law, Associativity for $\cap$, and the fact that two sets are disjoint iff one set is contained in the complement of the other, we get \begin{align} (A\cap B)\subseteq C &\iff (A\cap B)\cap C^c=\emptyset\\ &\iff A\cap (B\cap C^c)=\emptyset\\ &\iff A\cap (B^c\cup C)^c=\emptyset\\ &\iff A\subseteq (B^c\cup C)\\ &\iff A\subseteq[(X\smallsetminus B)\cup C]. \end{align}


Here, the right hand side of $\Ref{0}$ is the more complex one. So, let's calculate: $$\calc A \;\subseteq\; (X \setminus B) \cup C \op\equiv\hint{definition of \;\subseteq\;} \langle \forall x :: x \in A \;\then\; x \in (X \setminus B) \cup C \rangle \op\equiv\hint{definitions of \;\cup,\setminus\;} \langle \forall x :: x \in A \;\then\; (x \in X \land x \not\in B) \;\lor\; x \in C \rangle \op\equiv\hint{using \;A \subseteq X\;, so \;x \in A \then x \in X\;; simplify} \langle \forall x :: x \in A \;\then\; x \not\in B \;\lor\; x \in C \rangle \op\equiv\hints{write \;P \then Q\; as \;\lnot P \lor Q\;}\hint{-- to bring \;A\; and \;B\; together, as in the LHS of \Ref{0}} \langle \forall x :: x \not\in A \;\lor\; x \not\in B \;\lor\; x \in C \rangle \tag{*} \op\equiv\hints{write \;\lnot P \lor Q\; as \;P \then Q\;; DeMorgan}\hint{-- to better match the LHS of \Ref{0}} \langle \forall x :: x \in A \;\land\; x \in B \;\then\; x \in C \rangle \op\equiv\hint{definition of \;\cap\;} \langle \forall x :: x \in A \cap B \;\then\; x \in C \rangle \op\equiv\hint{definition of \;\subseteq\;} A \cap B \;\subseteq\; C \endcalc$$

This completes the proof.

Note the nice symmetry in this proof, centered around $\Ref{*}$: everything up until that point has been expanding definitions and simplifying. Also note that we didn't need the assumption that $\;B,C \subseteq X\;$. Finally, if you're curious, the above proof notation was designed by Edsger W. Dijkstra et al.; see for example EWD1300.