A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
|A₁ ∪ A₂ ∪ ⋯ ∪ Aₙ| = Σ|Aᵢ| - Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| - ⋯. This principle counts elements in unions by alternating sums of intersections, correcting for over-counting.
Start with two or three sets and draw Venn diagrams. Build understanding with counting problems (e.g., numbers divisible by 2 or 3).
When you want to count how many elements belong to at least one of several sets, simply adding up the set sizes overcounts: any element in two or more sets gets counted multiple times. The inclusion-exclusion principle corrects for this systematically. Start with the sum of individual set sizes (include all), subtract the pairwise intersections (exclude the double-counting), add back the triple intersections (you subtracted those three times but only needed to subtract twice), and continue alternating signs. The pattern of adding and subtracting is what gives the principle its name.
The two-set case is the clearest starting point: |A ∪ B| = |A| + |B| − |A ∩ B|. In a Venn diagram, the overlap region A ∩ B gets counted once in |A| and once in |B|, so you subtract it once to arrive at the correct total. For three sets: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. The triple intersection was over-subtracted by the pairwise terms, so you add it back. A concrete example using counting fundamentals you already know: how many integers from 1 to 100 are divisible by 2 or 3? Set A has 50 (divisible by 2), set B has 33 (divisible by 3), and A ∩ B has 16 (divisible by 6). The answer is 50 + 33 − 16 = 67.
The general formula |A₁ ∪ ⋯ ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| − ⋯ ± |A₁ ∩ ⋯ ∩ Aₙ| alternates in sign by the size of the intersection: singletons are positive, pairs negative, triples positive, and so on. A useful check: any element belonging to exactly m of the sets gets counted C(m,1) − C(m,2) + C(m,3) − ⋯ = 1 time in the final sum — a binomial identity guarantees this. This is the internal consistency that makes the formula correct.
The most common errors are sign errors and forgetting intersection terms, especially when the number of sets is large. A disciplined approach helps: list all singletons, then all pairs, then all triples, and so on, computing each intersection count carefully before assembling the alternating sum. Inclusion-exclusion is both a formula and a proof technique — many advanced combinatorial results, including counting derangements and surjections, are derived by choosing the right sets Aᵢ and applying this principle to their union's complement.