I want to prove the inclusion exclusion principle: |A∪B|=|A|+|B|−|A∩B| where A and B are finite sets.
However I'm confused about one thing. I've learned that two cardinalities are equal if there is a bijection over them... So how would I apply that in this situation?
I guess I can break A U B into |A| and |B| to look at them separately.... like many of the online solutions.
Finding a solution isnt very difficult, but I want to know WHY the solution is doing what it is doing.
Thanks!
We can do this by partitioning into disjoint subsets. That is, we'll use the fact that:
If $X$ and $Y$ are disjoint, then: $$ |X \cup Y| = |X| + |Y| $$
Now since: \begin{align*} A &= (A \cap B) \cup (A \setminus B) \\ B &= (A \cap B) \cup (B \setminus A) \\ A \cup B &= (A \setminus B) \cup (A \cap B) \cup (B \setminus A) \end{align*} where any two of the sets being unioned are disjoint, it follows that: \begin{align*} |A| + |B| - |A \cap B| &= (|A \cap B| + |A \setminus B|) + (|A \cap B| + |B \setminus A|) - |A \cap B| \\ &= |A \setminus B| + |A \cap B| + |B \setminus A| \\ &= |A \cup B| \end{align*}
On a Venn diagram, the area of two overlapping ovals is the sum of the area of each oval minus the area of the overlap.
The same principle holds for finite sets.
The measure of the union of two sets is the sum of the measures of each set minus the measure of the intersection of the two sets.
$$|A\cup B| = |A| + |B| - |A\cap B|$$
