Show that $|A \cup B| + |A \cap B|= |A| + |B|$ for two finite sets $A$ and $B$.
Can you please check the proof below, and let me know if it's right? It makes me a bit uneasy for some reason, and I can't tell why.
My givens are:
- $|A|$ is defined as $n$ if there is a bijection $f: A \to \{1,2,\dots,n\}$. The cardinality of an empty set is 0.
- If there is some bijective $f: A \to B$ and a bijective $g: B \to C$, then there exists some $h: A \to C$ such that $h$ is also bijective.
- Rudimentary results about sets from Chapter 1 of the text I'm using.
We show this by decomposing $|A \cup B| + |A \cap B|$ into disjoints units.
First, $|A \cup B| = |A-B| + |B-A| + |A \cap B|$ where each segment of the RHS is disjoint. From this, we can write
\begin{eqnarray} |A \cup B| + |A \cap B| &=& |A-B| + |B-A| + |A \cap B| + |A \cap B| \\ &=& (|A-B| + |A \cap B|) + (|B-A| + |A \cap B|) \\ &=& |A| + |B|\\ \end{eqnarray}