2
$\begingroup$

I was working on this assignment and was wondering if an assumption I made was correct and if my proofs as a whole were correct. The first part of the question was:

Use the algebraic method to prove the following set equality: $A∪B-B=A-B$

I've done this part already and use the result of said proof to formulate the start of the next proof.

Let $A$ and $B$ be two sets. Prove that $(A\cup B)-B=A$ iff $A$ and $B$ are disjoint.

Based on the previous proof:

$Let:(A∪B)-B=A-B=A$

$1)\ A-B=A\cap\bar B\text{; by Set Difference}$

$2)\ A\cap\bar B=A\cap(\bar B\cup\emptyset) \text{; by Identity}$

$3)\ A\cap(\bar B\cup\emptyset)=A\cup\overline{(B\cap\bar\emptyset)}\text{; by DeMorgan’s Law}$

$4)\ A\cup\overline{(B\cap\bar\emptyset)}=A\cup\overline{(B\cap U)}\text{; by 0/1 Law}$

$5)\ A\cup\overline{(B\cap U)}=A\cup\bar B\text{; by Identity}$

$6)\text{ Then, } A\cap\bar B=A\cup\bar B=A,\text{ which can only be true if }\bar B=A\text{; by Repetition Law}$

$7)\ \bar B=A\text{ implies }B\subseteq\bar A \therefore A\text{ and }B\text{ must be disjoint.}$

I'm wondering if this proof is acceptable (especially the conclusion I draw from points 6 and 7) or if I'm missing out on something (first time taking a course that wants rigorous proofs). Thanks!

$\endgroup$
  • 1
    $\begingroup$ I think you've misused DeMorgan's Law. $\endgroup$ – Cameron Williams Feb 23 '15 at 0:56
  • $\begingroup$ @CameronWilliams In step 3? Does DeMorgan's only apply to two arguments? I might have mixed it up with finding the dual. Hmm... $\endgroup$ – Terry Chern Feb 23 '15 at 0:59
1
$\begingroup$

You've misused DeMorgan's Law. There is an easier way to proceed. You've already noted that $(A\cup B)- B = A-B$. Thus we want to prove that $A-B = A$ if and only if $A,B$ are disjoint. I'll prove one direction and leave you to prove the other.

I'll prove that if $A-B=A$ then $A$ and $B$ are disjoint. To do so, I'll proceed by contrapositive; that is, I'll prove that if $A$ and $B$ are not disjoint, then $A-B\neq A$. If $A$ and $B$ are not disjoint, then there is $a\in A\cap B$. Thus $a\not\in A-B$. So $A-B\neq A$ since $a\in A$ but $a\not\in A-B$.

The other direction is simple. Don't get hung up on using set operations so heavily. It can make a simple proof rather complicated and difficult to piece together.

$\endgroup$
  • $\begingroup$ Thanks, this makes a lot more sense and is a lot easier to approach. The class I'm taking is discrete math for CS majors so we haven't really covered the stuff in lots of detail. The majority of what we do we use set operators, so I wouldn't have thought to just look at the elements. Thanks a bunch! $\endgroup$ – Terry Chern Feb 23 '15 at 1:07
  • $\begingroup$ No problem! I think I cleaned up the argument a little bit so it might be slightly easier to understand. $\endgroup$ – Cameron Williams Feb 23 '15 at 1:08
1
$\begingroup$

I'd like to say: "You've misused DeMorgan's Law. There is an easier way to proceed." :)

Now: $A∪B-B=A \iff$ $$A-B=A\iff A\cap B^c=A \iff A\subset B^c $$ $\iff$ $A$ and $B$ are disjoint

$\endgroup$
1
$\begingroup$

Since you have your answer, I thought I would show another way to go about it: you can do a truth table.

$$\begin{array}{lllll} A&B&(A\text{ or }B)&\text{Not }B&(A\text{ or }B)\text{ and }(\text{Not }B)\\ \hline T&T&T&F&F\\ T&F&T&T&T\\ F&T&T&F&F\\ F&F&F&T&F \end{array}$$

The first line doesn't matter. We can throw it out because $A$ and $B$ are to not have an element $x$ in common. The top line is basically saying $x$ is in $A$ and $x$ is in $B$ and we don't have that case here.

Other than that $A\equiv(A\text{ or }B)\text{ and }(\text{Not }B)$ are the same thing as long as the $A$ and $B$ are disjoint as we given.

$\endgroup$
  • $\begingroup$ The truth table was good for verification but the problem specifically requested for an algebraic solution. Thanks though! $\endgroup$ – Terry Chern Feb 23 '15 at 18:22

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.