Having trouble with a discrete math question involving sets. Have been asked to prove:

(A∪B) - (C - A) = A ∪ (B - C)

This is what I have so far:

x ϵ A or x ∈ (B - C)

x ∈ A or (x ∈ B and x ∉ C )

This where I get stuck. I can see how to combine the x ∈ A or (x ∈ B) into (A∪B), but I do not know how to derive the other half. Please help.

  • 1
    $\begingroup$ Considered just filling in a Venn diagram for each of the sides and seeing that the same areas of the diagram end up shaded? $\endgroup$ – Henning Makholm Dec 4 '14 at 18:23
  • 1
    $\begingroup$ In our course Venn diagrams cannot be used for proofs. $\endgroup$ – KleinBottle Dec 4 '14 at 18:25
  • $\begingroup$ x @isomorphism: How about truth tables, then? $\endgroup$ – Henning Makholm Dec 4 '14 at 18:26
  • $\begingroup$ No. A formal proof is required. $\endgroup$ – KleinBottle Dec 4 '14 at 18:26
  • 3
    $\begingroup$ x @isomorphism: What's informal about truth tables? If you want a proof in a particular formal proof system, you need to disclose which rules the proof systems you use has. $\endgroup$ – Henning Makholm Dec 4 '14 at 18:27

Assume that $x \in A \cup (B - C)$. Then ($x \in A$) OR $(x \in B$ and $x \notin C$).

If $x \in A$, then $x \in A \cup B$ and $x \notin C - A$, so $x \in (A \cup B) - (C-A)$.

If $x \in B$ and $x \notin C$, then $x \in A \cup B$ and $x \notin C - A$, so $x \in (A \cup B) - (C-A)$.

This means that $A \cup (B-C) \subset (A \cup B)-(C-A)$.

  • $\begingroup$ This solution is using the methods and notation that we learned in class. Thank you so much for helping out. $\endgroup$ – KleinBottle Dec 4 '14 at 18:44
  • $\begingroup$ What about the other direction? $\endgroup$ – Mars Dec 5 '14 at 3:33
  • $\begingroup$ D.J. proved the other direction. $\endgroup$ – desos Dec 5 '14 at 8:07

If you need a purely algebraic-looking proof, I would write $$ \begin{align} (A\cup B)\setminus(C\setminus A) &= (A\cup B)\setminus(C\cap A^\complement) \\&= (A\cup B)\cap (C\cap A^\complement)^\complement \\&= (A\cup B)\cap (C^\complement \cup A) \\&= A\cup(B\cap C^\complement) \\&= A\cup(B\setminus C) \end{align}$$

  • $\begingroup$ Would it be possible for you to complete the algebra? I'm not too familiar with your algebraic approach but I've seen the compliment notation and I'd like to learn this method as well. $\endgroup$ – KleinBottle Dec 4 '14 at 18:42
  • $\begingroup$ Thank you Henning, this is very helpful to add another technique to my tool kit. $\endgroup$ – KleinBottle Dec 4 '14 at 18:45
  • $\begingroup$ On an related note. What is the markup language or tool you guys are using for your data entry in these solutions? I need to graduate to math for web. $\endgroup$ – KleinBottle Dec 4 '14 at 18:48
  • $\begingroup$ @isomorphism: It's called MathJax and is largely the same input format as math mode in LaTeX. Here is a tutorial. $\endgroup$ – Henning Makholm Dec 4 '14 at 18:49
  • $\begingroup$ Great, thanks I will take a look. I've been dragging my heels with regard to learning LaTeX, but as an EE student I should probably learn some of it sooner rather than later. $\endgroup$ – KleinBottle Dec 4 '14 at 18:52

Proof of $\subseteq$:

Let $x \in (A \cup B) - (C - A)$. Then $x \in A$ or $x \in B$, and $x \notin (C-A)$. The last part means that either $x \in C \cap A$ or $x \notin C$.

Suppose $x \in C \cap A$. Then $x \in A$, so we're done as $A \subseteq A \cup (B-C)$.

Suppose $x \notin C$. But we also know that either $x \in A$ (in which case we're done) or $x \in B$ (in which case we're done, as $x \in (B-C)$).

I'll leave $\supseteq$ for you to try along similar lines.

  • $\begingroup$ Thanks D.J, this exercise is very helpful. $\endgroup$ – KleinBottle Dec 4 '14 at 18:45

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.