1
$\begingroup$

I recently started a Discrete Mathematics course in college and I am having some difficulties with one of the homework questions. I need to learn this, so please guide me through at least two steps to get the ball rolling.

The question reads: Show that if $A$ and $B$ are sets, then: $(A \cap B) \cup (A \cap B')=A$

We are supposed to use set identities. I had a question prior, but it was simple: $(A \cap B \cap C)' = A'\cup B' \cup C'$ - Which would be one of De Morgan's laws.

I am at a loss. I have been reading the textbook and tried looking up some videos, but I am not sure exactly where to start. Any help you can provide, will be greatly appreciated!

Thanks, Kei

$\endgroup$
  • $\begingroup$ I'm not sure what you're asking. Can you clarify what specifically you're confused with? Also I highly reccomend taking a look at "How to Prove It" as a supplementary text. It's a fantastic introduction to this subject. $\endgroup$ – lordoftheshadows Jan 23 '17 at 18:58
  • $\begingroup$ Use distributivity! LHS is equal to $A \cap (B \cup B')$ $\endgroup$ – Crostul Jan 23 '17 at 18:58
  • $\begingroup$ @lordoftheshadows: I wasn't sure on the first two steps to prove that the left side is indeed equal to the right side? If I am explaining it right. Our professor showed us an example in class such as this: (A ∪ (BnC))` = (C` ∪ B) ∩ A = A` ∩ (B ∩ C) - De Morgan Law = A` ∩ (B` u C) De Morgan Law = (B u C) ∩ A = Commutative Law = (C` u B) ∩ A = Commutative Law So I am looking for the first two steps, I see that @Crostul had posted the first step. Thank you! I am going to see if I can take it from there. I do really appreciate the help! $\endgroup$ – Kei U. Jan 23 '17 at 19:00
  • $\begingroup$ I have edited the question for formatting and some grammatical things for you, @KeiU. We will all see it when it is approved. Good luck! $\endgroup$ – The Count Jan 23 '17 at 19:03
  • $\begingroup$ Thank you @TheCount! I appreciate that, I really should have looked over the question better, sorry! @Crostul: Do I distribute (A ∩ B) U (A ∩ B`) together? $\endgroup$ – Kei U. Jan 23 '17 at 19:05
3
$\begingroup$

The idea is to achieve get close $B$ and $B^c$. Then we use distributive property: $(A\cap B)\cup(A\cap B^c)=A\cap (B\cup B^c)=A\cap X=A $, with $X$ the universe

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hello, I really appreciate your answer you provided! I think where I was confused was, being able to reverse an identity. I was using the set identity, though not using it in reverse if that makes sense. This is what I did: I used Distributive law, Absorption law, and then Identity law. $\endgroup$ – Kei U. Jan 23 '17 at 19:24
  • $\begingroup$ It would not let me edit the above comment. The last sentence should be a question. I wanted to ensure that I did use the right laws above, as you shown in your post Julio Maldonado Henriquez. Thank you! $\endgroup$ – Kei U. Jan 23 '17 at 19:33
0
$\begingroup$

Consider an element of $A$ - either it is in $B$, or it isn't, and thus is in the complement of $B$. Thus $A \subset (A \cap B)$ $\cup$ $(A \cap B')$. Now, try to argue on your own that the reverse "inclusion" holds: that we have $A \supset (A \cap B)$ $\cup$ $(A \cap B')$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

You can use identities such as $(A\cap B) \cup (A \cap C) = A \cap (B \cup C)$ to get $(A \cap B) \cup (A \cap B') = A \cap (B \cup B') = A \cap U = A$.

But I prefer to think of what it is saying. $A \cap B$ means "everything in A and in B" and $A \cap B'$ means "everything that is in A that is not in B" and $(A\cap B) \cup (A \cap B')$ means "every thing that is in A and B combined with everything that is not in B". Is there a logical reason that "everything in A and B combined with everything in A and not in B" would be "A"?

Well, I hope it should be obvious. Everything in A is either in B or not in B so combining the items of A that are not in B with those that are should give you all the items in A.

So the best way to express that idea directly would be:

$A = A \cap U = A \cap (B \cup B') = (A \cap B) \cup (A\cap B')$. Or if that's a little too abstract, I rather like to do an element by element proof:

Let $x \in A$ either $x \in B$ or $x \in B'$. If $x \in B$ then $x \in A \cap B$. If $x \in B'$ then $x \in A \cap B'$. Either way $x \in A \cap B$ or $x \in A\cap B'$ so $x \in (A \cap B) \cup (A\cap B)$. So $A \subseteq (A\cap B) \cup (A \cap B)$. Likewise if $y \in (A \cap B) \cup (A\cap B)$ then either $y \in (A \cap B) \subset A$ or $y \in (A\cap B') \subset A$. Either way, $y \in A$ so $(A\cap B)\cup (A\cap B') \subseteq A$.

$A \subseteq (A\cap B) \cup (A \cap B)$ and $(A\cap B)\cup (A\cap B') \subseteq A$, so $$(A\cap B)\cup (A\cap B') = A$.

A fourth way is the big guns.

Let $x \in U$ now one of four things might happen:

1) $x \in A$ and $x \in B$. Then $x \in A$ and $x \in A\cap B$ and $x \in (A \cap B) \cup (A \cap B')$.

2) $x \in A$ and $x \not \in B$. Then $x \in A$ and $x \in B'$ and $x \in A \cap B'$ and $x \in (A \cap B) \cup (A \cap B')$

3) $x \not \in A$ and $x \in B$. Then $x \not \in A$ and $x \not \in A \cap B$ and $x \not \in A \cap B'$ so $x \not \in (A \cap B) \cup (A \cap B')$.

4) $x \not \in A$ and $x \not \in B$. Then $x \not \in A$ and $x \not \in A \cap B$ and $x \not \in A \cap B'$ so $x \not \in (A \cap B) \cup (A \cap B')$.

Looking at the four cases we see $x \in A \iff x \in (A \cap B) \cup (A \cap B')$. Thus $A$ and $(A \cap B) \cup (A \cap B')$ have precisely the same elements and neither has any element the other doesn't. In other words, $A = (A \cap B) \cup (A \cap B')$.

| cite | improve this answer | |
$\endgroup$

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.