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.

  • 1
    $\begingroup$ Is $\overline{B}$ the complement of $B$? $\endgroup$ – Martin Feb 8 '13 at 11:45
  • $\begingroup$ Yes... that's correct. So U-B, (Universe minus B) $\endgroup$ – Nicholas Feb 8 '13 at 12:05
  • $\begingroup$ @Martin I was very confused when going through the answers, though it was the closure of $B$ xD $\endgroup$ – DanZimm May 24 '13 at 23:07
  • $\begingroup$ @DanZimm: I agree, it's terrible notation :-) $\endgroup$ – Martin May 24 '13 at 23:08
  • 1
    $\begingroup$ @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 :-) $\endgroup$ – 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.

  • $\begingroup$ Damn... nice work $\endgroup$ – 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 $(*)$.


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.