Inclusion-Exclusion for Three Sets
What you'll learn: You'll extend the two-set inclusion-exclusion principle to count elements in the union of three sets by alternating additions and subtractions.
The Core Idea
When counting elements in the union of three sets A, B, and C, you can't just add up their sizes—you'll overcount! Elements in overlaps get counted multiple times. The Inclusion-Exclusion Principle for Three Sets corrects this by:
- Adding the sizes of individual sets (|A| + |B| + |C|)
- Subtracting the pairwise intersections (−|A∩B| − |A∩C| − |B∩C|), since we counted these twice
- Adding back the three-way intersection (+|A∩B∩C|), since we subtracted it too many times
The formula:
|A ∪ B ∪ C| = |A| + |B| + |C|
− |A∩B| − |A∩C| − |B∩C|
+ |A∩B∩C|
Why the Alternating Pattern?
Think of it like adjusting a balance scale:
- Start by adding all sets (overcounts overlaps)
- Subtract pairs (corrects double-counts, but now elements in all three sets have been removed entirely!)
- Add back the triple intersection (restores those wrongly-removed elements)
Each element in A∩B∩C is counted: +1 (from A) +1 (from B) +1 (from C) −1 (from A∩B) −1 (from A∩C) −1 (from B∩C) +1 (from A∩B∩C) = exactly 1 time.
Example
If |A|=50, |B|=40, |C|=30, |A∩B|=10, |A∩C|=8, |B∩C|=7, |A∩B∩C|=3:
|A ∪ B ∪ C| = 50 + 40 + 30 − 10 − 8 − 7 + 3 = 98
Key Takeaway: The inclusion-exclusion principle for three sets uses alternating signs—add individual sets, subtract pairs, add triples—to count union elements exactly once.