Let $A, B$ be finite sets. Show that $A \cup B = (A$ \ $B ) \cup (A \cap B) \cup (B$ \ $A)$.

Deduce that $|A| + |B| = |A \cup B| + |A \cap B|$

These are obvious when considering Venn diagrams but I'm at a lose on even how to start to show this algebraically.

I've tried re-writing $(A$ \ $B ) \cup (A \cap B) \cup (B$ \ $A)$ as $(A \cap \neg B) \cup (A \cap B) \cup (B \cap \neg A)$ but I don't know where to go from there.

Any help would be appreciated. Thank you.

  • $\begingroup$ What is $\neg B$ for a set? $\endgroup$ – martini Jul 29 '14 at 8:24
  • $\begingroup$ @martini I meant everything that's not inside the set B. $\endgroup$ – Elise Jul 29 '14 at 8:34

Use distributivity laws. For example:

$$(A\cap \neg B)\cup(A\cap B) = (A\cup A) \cap (A\cup B)\cap(A\cup \neg B) \cap (B\cup \neg B) =\\ =A\cap (A\cup B) \cap (A\cup \neg B)\cap U$$ Now, since $U$ is the universal set, $U\cap X=X$ for any $X$. Also, since $A\subseteq A\cup B$, you know that $A\cap (A\cup B)=A$, so you get $$A\cap(A\cup \neg B)$$ and again, vecause $A\subseteq A\cup\neg B$, you have $A\cap(A\cup\neg B)=A$, so in conclusion:

$$(A\cap \neg B)\cup (A\cap B) = A.$$

  • $\begingroup$ Thank you. Would I be correct in carrying it on to say: $A \cup (B \cap \neg A) = (A \cup B) \cap (A \cup \neg A) = (a \cup B) \cap U = A \cup B$ $\endgroup$ – Elise Jul 29 '14 at 9:06
  • 1
    $\begingroup$ @Elise Very good! you are finished! $\endgroup$ – 5xum Jul 29 '14 at 9:08

On one hand $$ A\setminus B, A \cap B \subseteq A \subseteq A \cup B, \qquad B \setminus A \subseteq B \subseteq A \cup B $$ hence "$\supseteq$" holds.

Now let $x \in A \cup B$. Then $x \in A$ or $x \in B$. If $x \in A$, then either $x \in B$ and hence $x \in A \cap B$ or $x \not\in B$ hence $x \in A \setminus B$. If $x \not\in A$, then as $x \in A \cup B$ we must have $x \in B$ and hence $x \in B \setminus A$. So in all cases $x \in (B \setminus A) \cup (A \cap B) \cup (A \setminus B)$. This proves "$\subseteq$".

  • $\begingroup$ Thank you. I understand your second paragraph - which is a really nice way of doing it - but I don't understand what you mean by "hence "$\supseteq$" holds"? $\endgroup$ – Elise Jul 29 '14 at 9:11
  • $\begingroup$ As we know (as I wrote) $A -B, A \cap B, B-A \subseteq A \cup B$, we have $$ A \cup B \supseteq (A-B)\cup (A\cap B) \cup (B-A) $$ which is one inclusion of the two we need for the equality you stated (namely "$\supseteq$"). $\endgroup$ – martini Jul 29 '14 at 10:52

you can't whisk a proof out of thin air! so what assumption are you starting from? the most reasonable assumption is that if two sets $X$ and $Y$ are mutually disjoint then $$ |X \cup Y | = |X| + |Y| \tag{1} $$ see if you can solve the problem using this assumption.


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.