2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – pjs36 Feb 1 '17 at 15:53
3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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} $$

$\endgroup$
0
$\begingroup$

Here is an element-level or 'element chasing' proof. But let's first write down the statement a bit more formally: given $\;A,B,C \subseteq X\;$, prove $$ \tag{0} A \cap B \subseteq C \;\equiv\; A \subseteq (X \setminus B) \cup C $$ For statements like this, it is often helpful to start at the most complex side, and use simplification to work towards the other side. And for set theory proofs, it often helps me to be able to reason at the level of logic.$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\Ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} $

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.