Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I really need help with this logical proof.

Show that $A-B \subseteq C \Rightarrow A\cup B \subseteq B\cup C$.

Please show the steps to the solution. Thank you!

share|improve this question

5 Answers 5

up vote 5 down vote accepted

I won't provide a full solution with all steps, but I can give you a fairly strong

Hint: If $x \in A \cup B$ then either $x \in B$ or $x \notin B$. If $x \in B$, then clearly $x \in B \cup C$. However, if $x \notin B$, then to which set mentioned in the problem does it belong?

share|improve this answer

Let $x\in A\cup B$. Then either $x\in B$, or $x\not\in B$ so $x\in A$. In the second case, $x\in A-B$ so $x\in C$. The result follows.

share|improve this answer

Call $D=A\cup B$, then $D=(D\cap B)\cup (D\cap B^c)$, where $^c$ denotes the complement. Here $D\cap B=(A\cap B)\cup (B\cap B)=(A\cap B)\cup B$ and $D\cap B^c=(A\cap B^c)\cup( B\cap B^c)=A\cap B^c$. Can you take it from here?

share|improve this answer

One more approach is via the properties of union: it is order-preserving with respect to the inclusion, which means that $X \subseteq Y \Rightarrow X\cup Z \subseteq Y \cup Z$. However, we have $(A - B) \cup B = A \cup B$ and that completes the proof.

share|improve this answer

A calculational approach to this old question: translate from the level of sets to the level of elements, using the definition of $\subseteq$. For the second expression, we get $$ \begin{align} & A \cup B \;\subseteq\; B \cup C \\ \equiv & \;\;\;\;\;\text{"definition of $\subseteq$"} \\ & \langle \forall x :: x \in A \cup B \;\Rightarrow\; x \in B \cup C \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\cup$, twice"} \\ & \langle \forall x :: x \in A \lor x \in B \;\Rightarrow\; x \in B \lor x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"logic: expand $\Rightarrow$, and apply DeMorgan to its left hand side"} \\ & \langle \forall x :: (x \not\in A \land x \not\in B) \lor x \in B \lor x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"logic: use negation of $x \in B$ in other part of $\lor$"} \\ & \langle \forall x :: (x \not\in A \land \textrm{true}) \lor x \in B \lor x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ & \langle \forall x :: x \not\in A \lor x \in B \lor x \in C \rangle \\ \end{align} $$ Now doing the same with the other expression, we get $$ \begin{align} & A - B \;\subseteq\; C \\ \equiv & \;\;\;\;\;\text{"definition of $\subseteq$"} \\ & \langle \forall x :: x \in A - B \;\Rightarrow\; x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $-$"} \\ & \langle \forall x :: x \in A \land x \not\in B \;\Rightarrow\; x \in C \rangle \\ \equiv & \;\;\;\;\;\text{"logic: expand $\Rightarrow$, and apply DeMorgan to its left hand side"} \\ & \langle \forall x :: x \not\in A \lor x \in B \lor x \in C \rangle \\ \end{align} $$

In both cases we end up with the same result, and therefore we have proven something sronger than originally asked: $$ A \cup B \;\subseteq\; B \cup C \;\;\equiv\;\; A - B \;\subseteq\; C $$

Note how the above calculations were driven by two principles: first, the desire to work at the element level using logic, as opposed to the level of sets; second, simplify where possible. Also note that $\Rightarrow$ usually is a difficult operator to calculate with, so often (like here) I will quickly expand $P \Rightarrow Q$ into the equivalent $\lnot P \lor Q$.

share|improve this answer
    
The statement can be proven in two lines of element chasing. This sort of argument is unnecessary. –  Vectk Apr 30 '13 at 7:41
    
@Brian Could you show such a proof in an answer of your own? Is my proof unnecessarily complex? My goal in proofs like this is to minimize the number of surprises for the reader. Is my proof unnecessarily long? All in all, leaving out the hints (which in 'standard' proofs are also left out) my proof is about 150 characters, and I have spelled out several steps which I would normally skip. Or does my proof use unnecessary mechanisms? Thanks! –  Marnix Klooster Apr 30 '13 at 7:54
    
The proof is simple. Let $x \in A \cup B$. If $x \in B$, then $x \in B \cup C$. If $x \notin B$, then $x \in A \setminus B$, so $x \in C \subset B \cup C$. In any case $x \in B \cup C$, so $A \cup B \subset B \cup C$. That's it. Your proof is needlessly complicated and will likely confuse the OP. –  Vectk Apr 30 '13 at 22:34
    
Thanks! Yes, that is shorter. My main gripe is the 'surprise' in proofs like yours: why did you decide to split on $x\in B$ and $x\not\in B$? This makes the proof appear like a trick to the reader, while a straightforward calculation (as in my proof) also works. Also, "then $x\in A\backslash B$" looks trivial, but here the reader really has to understand how to use $x\in A\cup B$. Finally, your proof is half the length of mine, but my proof also proves the other direction. @user1442762 As the OP, I'm genuinely curious whether you find my proof needlessly complicated and confusing. –  Marnix Klooster May 1 '13 at 6:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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