# Proof in set theory

Let $A,B,C$ -- subsets in some fixed set. Prove that $A \cap B \subseteq C$ iff $A \subseteq \overline{B} \cup C$.

Have no ideas how to prove this. On the language of definitions we have $$x \in (A \land B) \Rightarrow x \in C \Leftrightarrow x \in A \Rightarrow x \in (\overline{B} \lor C).$$

But it's the only I can do...

## 2 Answers

$(\Rightarrow)$ Assume $A\cap B\subseteq C$. Let $x\in A$. Then if $x\in B$, $x\in C$ by hypothesis. Otherwise, $x\in \bar B$. Thus, $x\in \bar B\cup C$, and $A\subseteq \bar B\cup C$.

$(\Leftarrow)$ Assume that $A\subset\bar B\cup C$. Let $x\in A\cap B$. Then $x\in A$, so by hypothesis, $x\in \bar B$ or $x\in C$. But we know that $x\in B$ by assumption, so $x\not\in \bar B$. Thus, $x\in C$, and $A\cap B\subseteq C$.

If $A\cap B\subseteq C$ and $x\in A$ then two possibilities can be discerned:

• $x\notin B$ wich is the same as $x\in\overline B$.
• $x\in B$ then $x\in A\cap B\subseteq C$ so that $x\in C$.

In both cases $x\in\overline B\cup C$.

If conversely $A\subseteq\overline B\cup C$ then $A\cap B\subseteq(\overline B\cup C)\cap B=(\overline B\cap B)\cup (C\cap B)=C\cap B\subseteq C$.