# Cardinality of the Union of an Indexed Collection of Sets

I am taking Abstract Algebra right now and working on the exercises in the introductory section on Set Theory. I am having trouble proving the following question although it makes intuitive sense to me due to the intersection either being occupied by an even number or odd number of sets in the collection, leading to the alternating plus and minus sign.

Prove that $$\left| \bigcup_{i=1}^{n} A_{i} \right| = \sum_{i=1}^{n} |A_{i}| - \sum_{1 \leq i < j \leq n} |A_{i} \cap A_{j}| \\ + \sum_{1 \leq i < j < k \leq n} |A_{i} \cap A_{j} \cap A_{k}| - \sum_{1 \leq i < j < k < l \leq n} |A_{i} \cap A_{j} \cap A_{k} \cap A_{l}| + \cdot \cdot \cdot$$

Any ideas on how I can prove this?

-
Inclusion Exclusion –  Amr Feb 5 '13 at 4:20

Hint: If you wanted to find how many things were in a union $\displaystyle \bigcup A_n$ you'd say "ok, well there are $\displaystyle \sum_n |A_n|$ things". You then realize that you've double counted, so you have to get rid of the double counts, so you subtract $\displaystyle \sum_{i,j}|A_i\cap A_j|$. You then realize that you could have double counted some of the double counts (if an element is a double count for two separate sets) and so you have to add in the double counts of the double counts so you add back in $\displaystyle \sum_{i,j,k}|A_i\cap A_j\cap A_k|$ and then you...
I realize that this is how you do the question, as this is the intuitive way that the question makes sense to me, but how do I write out a rigorous proof? It's similar to how I can argue that the cardinality of the power set of a set should be $2$ to the power the cardinality of that set since you either pick an element in a subset or you don't, but I have a difficult time formalizing the proof algebraically. –  Samuel Reid Feb 5 '13 at 4:26