Tell me more ×
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.
up vote 0 down vote favorite

We were ask to prove that $|A \cup B| = |A| + |B| - |A \cap B|‫‪$. It was easy to prove it using a Venn diagram, but I think we might be expected to do if more formally. Is there a formal way?

share|improve this question
What does $|A|$ mean? Is $|\cdot|$ a measure? Or maybe the sets are finite? – Jeff Nov 14 '11 at 16:44
2  
just observe that if you do $|A|+|B|$ you count twice the elements in $A\cap B$. – Valerio Capraro Nov 14 '11 at 16:48
Suppose that you want to give a dollar to everyone in $A\cup B$. If you give a dollar to everyone in $A$, and then give a dollar to everyone in $B, \dots$. – André Nicolas Nov 14 '11 at 17:21
I am fairly certain that this question appeared here perhaps infinitely many times before. I cannot find it though... – Asaf Karagila Nov 14 '11 at 18:22

1 Answer

up vote 4 down vote accepted

$A\cup B = (A\setminus B) \cup (B\setminus A) \cup (A\cap B)$. These three sets are disjoint, so $$ |A\cup B| = |A\setminus B| + |B\setminus A| + |(A\cap B)| $$ But $A\setminus B = A\setminus(A\cap B)$, so $|A\setminus B|=|A|-|A\cap B|$. A similar equality holds for $|B \setminus A|$. Substitution of these into the displayed equation above yields your result.

Of course, one might need to formally show that $|A\setminus (A\cap B)| = |A|-|A\cap B|$. I can't decide if this is any less obvious than the original proposition...

share|improve this answer
2  
I have seen $A \setminus B$, $A \smallsetminus B$ and $A - B$ used to denote set difference, but not $A / B$. Do you normally use that notation? =) – Srivatsan Nov 14 '11 at 16:59
1  
Is using a forward slash for set difference standard notation? – Henning Makholm Nov 14 '11 at 17:00
3  
bleech... I'm left/right backslash challenged...I got points taken off for doing that on a topology test once. – David Mitra Nov 14 '11 at 17:00
@David Mitra: The forward slashes were bothersome, so I was changing things to setminus, and in the middle they changed to backslash. Not thinking, I continued. Can turn them to backslash if you wish. – André Nicolas Nov 14 '11 at 17:40
Thanks. \setminus is better of course. I'm not sure if \backslash is a mathop... – David Mitra Nov 14 '11 at 17:44

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.