Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Inclusion Exclusion –  Amr Feb 5 '13 at 4:20

2 Answers 2

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...

share|improve this answer
    
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
    
With arguments like this, I don't find that an intuitive counting argument is actually non-rigorous. –  Alex Youcis Feb 5 '13 at 4:27
    
so it would be okay to write something like this on an exam? –  Samuel Reid Feb 5 '13 at 4:28
    
@SamuelReid Now that's a loaded question if I ever did hear one. This highly depends on the style of your professor and the setting of the class. If it were me though, and you polished what I said in my post a little more I would be ok. Like I said though, this really depends on the teacher/grader. –  Alex Youcis Feb 5 '13 at 4:30

This is the inclusion-exclusion theorem; you’ll find two proofs in the linked article.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.