I'm asked to prove the statement in the title under the assumption that I do not know the Inclusion-Exclusion Principle. I have two ways of starting the proof where:
- I could declare two sets with a certain amount of values and show by example that it is true:
$A = \{1. 2, 3, 4\}$ and $B = \{3, 4, 5, 6\}$
$|A| = 4$, $|B| = 4$
$|A \cup B| = |A| + |B| - |A \cap B| = 4 + 4 - 2 = 6$
- I could state that it is true and give a logical explanation:
This is true, because to count the number of elements in $A \cup B$, we start by counting those in $A$, and then add those in $B$. If $A$ and $B$ were disjoint, then we are done, otherwise, we have double counted those in both sets, so we must subtract those in $A \cap B$.
However, I don't know if these are counted as formal proofs. If not, how would I start a proof like this?
Preliminary: I will use the rather classical notation: $E \backslash F$ for the set of elements that belong to $E$ but not to $F$.
You need to write $A \cup B$ as a disjoint union (said otherwise, a partition of $A \cup B$):
$$A \cup B=(A \backslash B) \cup (A \cap B) \cup (B \backslash A)$$
to which you can apply:
$$|A \cup B|=|A \backslash B| + |A \cap B| + |B \backslash A| \tag{1}$$
For the same reason, you can say that:
$$|A \cup B|=|A| + |B \backslash A| \tag{2}$$
$$|A \cup B|= |A \backslash B|+|B| \tag{3}$$
Now make the combination (2)+(3)-(1).