# Looking for a proper proof that two sets with sub sets are equivalent

Basically I would just like to know how to prove the following equation

$$A \subseteq B \cup C \iff A \cap \overline B \subseteq C$$

I understand that I have to prove that the left-hand side should equal the right-hand side, and I can perform all the basic logical equivalencies, like Association ad Distribution, but I am unsure how to express the subset ($\subseteq$) in the proof. I'm tempted to treat the subset sign as intersection ($\cap$), but since my proof doesn't work... I'm pretty sure this is the wrong approach.

• Is $\overline{B}$ the complement of $B$? – Martin Feb 8 '13 at 11:45
• Yes... that's correct. So U-B, (Universe minus B) – Nicholas Feb 8 '13 at 12:05
• @Martin I was very confused when going through the answers, though it was the closure of $B$ xD – DanZimm May 24 '13 at 23:07
• @DanZimm: I agree, it's terrible notation :-) – Martin May 24 '13 at 23:08
• @DanZimm: Both are common. Then there's the French way: $\complement B$ or the more precise $\complement_UB$ to emphasize the universal set $U$. But it's getting a bit off-topic :-) – Martin May 24 '13 at 23:12

Just "sweat the definitions" [almost always the best strategy faced with little problems like this.]

Assume $A \subseteq B \cup C$.

By definition, $A \subseteq B \cup C$ means that, take any $x$ in the relevant universe, if $x \in A$ then $x \in B \cup C$.

That is to say, if $x \in A$ then either $x \in B$ or $x \in C$ or both.

Propositional logic tells you then that if $x \in A$ and $x \notin B$, then we must have $x \in C$.

But that tells you that if $x \in A \land x \in \overline{B}$, then $x \in C$. [Assuming here that, for any $x$ in the relevant universe, $x \in \overline{B}$ iff $x \notin B$.]

So, by definition again (since $x$ was arbitrary), $A \cap \overline{B} \subseteq C$.

That gives you one direction of the biconditional you need to prove. You can prove the other direction in an exactly similar way.

• Damn... nice work – Nicholas Feb 8 '13 at 12:08

I completely agree with Peter Smith's advice to "sweat the definitions". Here is the way in which I would do this: start at the most complex side, expand the definitions, and see whether you can get to the other side.

Note that below, $x$ ranges over the 'universe' that is implicit in this question.

\begin{align} & A \cap \overline B \subseteq C \\ \equiv & \;\;\;\;\;\text{"definition of $\subseteq$"} \\ & \langle \forall x :: x \in A \cap \overline B \;\Rightarrow\; x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\cap$"} \\ & \langle \forall x :: x \in A \land x \in \overline B \;\Rightarrow\; x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\overline{\phantom\square}$"} \\ & \langle \forall x :: x \in A \land x \not\in B \;\Rightarrow\; x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"expand $\Rightarrow$, using De Morgan on its left hand side"} \\ (*) \; \phantom\equiv & \langle \forall x :: x \not\in A \;\lor\; x \in B \;\lor\; x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"reintroduce $\Rightarrow$ at the first $\lor$ -- suggested by the shape of our goal"} \\ & \langle \forall x :: x \in A \;\Rightarrow\; x \in B \lor x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\cup$"} \\ & \langle \forall x :: x \in A \;\Rightarrow\; x \in B \cup C \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\subseteq$"} \\ & A \subseteq B \cup C \\ \end{align}

This completes the proof.

So by expanding the definitions, and also writing $\Rightarrow$ which often is difficult to calculate with, we arrived at $(*)$. Then it was not difficult to see how we could get to the goal. Alternatively, one could also start at both ends and see that both end up at $(*)$.