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?
Size of a union of two sets
-
0I am fairly certain that this question appeared here perhaps infinitely many times before. I cannot find it though... – 2011-11-14
2 Answers
$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...
-
0Thanks. \setminus is better of course. I'm not sure if \backslash is a mathop... – 2011-11-14
Just elaborating on the last post,
$\begin{array}{l} A \cup B\\ = (A \cup {A^c}) \cap (A \cup B)\\ = A \cup ({A^c} \cap B)\\ = (A \cap (B \cup {B^c})) \cup ({A^c} \cap B)\\ = (A \cap B) \cup (A \cap {B^c}) \cup ({A^c} \cap B) \end{array}$
Note that these 3 sets are mutually disjoint, since
$\begin{array}{l} (A \cap B) \cap (A \cap {B^c}) = A \cap (B \cap {B^c}) = A \cap \Phi = \Phi \\ (A \cap B) \cap ({A^c} \cap B) = (A \cap {A^c}) \cap B = \Phi \cap B = \Phi \end{array}$
Hence, by basic addition rule for counting,
$\begin{array}{l} |A \cup B|\\ = |A \cap B| + |A \cap {B^c}| + |{A^c} \cap B|\;\;\;\;\;\;\ldots (1) \end{array}$
Again, we have
$\begin{array}{l} A = A \cap (B \cup {B^c}) = (A \cap B) \cup (A \cap {B^c})\\ B = (A \cup {A^c}) \cap B = (A \cap B) \cup ({A^c} \cap B) \end{array}$
Again, these 3 sets are mutually disjoint, as shown earlier. Hence, by basic addition rule for counting,
$\begin{array}{l} |A| = |A \cap B| + |A \cap {B^c}| \Rightarrow |A \cap {B^c}| = |A| - |A \cap B|\\ |B| = |A \cap B| + |{A^c} \cap B| \Rightarrow |{A^c} \cap B| = |B| - |A \cap B| \end{array}$
Hence, from (1), we get
$\begin{array}{l} |A \cup B|\\ = |A \cap B| + |A \cap {B^c}| + |{A^c} \cap B|\\ = |A \cap B| + |A| - |A \cap B| + |B| - |A \cap B|\\ = |A| + |B| - |A \cap B| \end{array}$ (Proved)