Inclusion-exclusion principle: Foundations — Maths deep dive

Before you can trust that recipe, you need to be fluent with a handful of symbols and pictures. This page builds all of them from zero, in the order the topic actually uses them. Nothing here assumes you have seen set notation before.

1. A "set" and how we draw it

The things inside a set are its elements (or members). If the number $3$ is an element of set $A$ , we write $3 \in A$ — read " $3$ is in $A$ ."

Read figure s01 now. The outer rectangle is the universe: every item we could possibly talk about. We write the universe as $S$ when we are thinking about it as a sample space of outcomes (the letter $S$ will return in the probability version, §10), and as $U$ when we simply mean a background universal set of things to count — they are the same box, just named for the mood we are in. Inside that box, the orange circle is set $A$ and the teal circle is set $B$ . The dot labelled " $3 \in A$ " sits inside circle $A$ ; the dots floating in the corners of the box belong to no set. This single picture — circles inside a box — is the stage on which the entire topic plays out. See Set Theory & Venn Diagrams for more of these drawings.

2. Counting a set: the "size" bars $∣ A ∣$

3. Union $\cup$ — "in at least one"

In the figure, the teal region is $A \cup B$ . Notice it includes the middle lens where the circles overlap — union keeps everything.

4. Intersection $\cap$ — "in all of them"

The orange lens in figure s02 is $A \cap B$ . This lens is the villain of the whole story: adding $∣ A ∣ + ∣ B ∣$ counts every dot in the lens twice, once from each circle. That is precisely why the two-set formula subtracts $∣ A \cap B ∣$ .

5. Many-set union and intersection: $⋃$ and $⋂$

The big $⋃$ and $⋂$ are just the small $\cup$ and $\cap$ repeated, exactly as $\sum$ (coming in §7) is $+$ repeated. A $k$ -fold intersection shrinks as $k$ grows — demanding membership in more circles keeps fewer elements — while a $k$ -fold union grows.

6. Disjoint sets and the empty set $\emptyset$

Recall Why disjoint is the "easy" case

If nothing is shared, nothing is double-counted, so you can just add: $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ . This is exactly the additivity idea behind the Probability Axioms.

7. Adding disjoint pieces — the rule addition depends on

Why the topic leans on this: the parent note splits $A \cup B$ into three disjoint pieces — "only $A$ ", "only $B$ ", and "both" — precisely so it can add them safely. Every inclusion–exclusion proof secretly reduces overlapping counting to disjoint counting. This is the backbone of Counting Principles & Combinatorics.

8. The summation sign $\sum$

The notation $\sum_{i < j}$ means "add over every pair $(i, j)$ with $i$ smaller than $j$ ", so each pair is counted once, never twice.

9. Choose numbers $(k n)$

Here $n!$ (" $n$ factorial") means $n \times (n - 1) \times \dots \times 1$ , and $0! = 1$ by convention. See Counting Principles & Combinatorics.

10. The alternating sign $(- 1)^{k + 1}$

The bars in the figure show the net contribution of one element that lives in $m = 3$ sets: $+ 3$ from singles, $- 3$ from pairs, $+ 1$ from the triple. They stack to exactly $1$ — the promise of the whole principle. This same cancellation is what powers Bonferroni Inequalities when you stop the sum early.

11. Probability $P (A)$ — sizes turned into fractions

Here $S$ is the very same box from figure s01 — now read as the sample space of all equally likely outcomes. Because dividing by $∣ S ∣$ changes nothing structural, every sign and every term carries over unchanged. This is the bridge to Probability Axioms.

How the foundations stack up

Read these bottom-to-top as a ladder: each rung only makes sense once the rung below is solid.

Sets drawn as circles in a box (§1) give us something to count.
Size bars $∣ A ∣$ (§2) let us count a circle.
Union $\cup$ and intersection $\cap$ (§3–4) describe combining two circles — the whole blob versus the shared lens.
Big $⋃$ and $⋂$ (§5) repeat those to many circles — the exact objects the general formula sums.
Pairwise-disjoint sets (§6) and the disjoint addition rule (§7) give the safe, no-overlap case that all counting reduces to.
$\sum$ (§8) and $(k n)$ (§9) let us write and count all those terms compactly.
The sign switch $(- 1)^{k + 1}$ (§10) makes the add–subtract–add dance precise.
Probability $P (A)$ (§11) reinterprets the whole thing as fractions of the box.

Together these pour directly into the Inclusion–Exclusion Principle.

Equipment checklist

Recall Are you ready? (reveal each answer)

A set is ::: a collection of distinct things, drawn as a circle inside the universe box. $∣ A ∣$ means ::: the number of elements in $A$ (its size), NOT absolute value. $A \cup B$ in words and picture ::: "in $A$ or $B$ or both"; shade the whole blob of both circles. $A \cap B$ in words and picture ::: "in both $A$ and $B$ "; shade only the overlap lens. $⋃_{i = 1}^{k} A_{i}$ means ::: items in at least one of $A_{1}, \dots, A_{k}$ — the whole combined blob of $k$ circles. $⋂_{i = 1}^{k} A_{i}$ means ::: items in every one of $A_{1}, \dots, A_{k}$ — the region where all $k$ circles overlap. Pairwise disjoint means ::: every two sets in the collection share no element (no lens between any pair). The disjoint addition rule says ::: for pairwise-disjoint sets, $∣ ⋃ A_{i} ∣ = \sum ∣ A_{i} ∣$ — just add. $\sum_{i = 1}^{n} ∣ A_{i} ∣$ means ::: add $∣ A_{1} ∣ + ∣ A_{2} ∣ + \dots + ∣ A_{n} ∣$ ; the $i < j$ version adds over each pair once. $(k n)$ means ::: the number of ways to choose $k$ items from $n$ , equal to $\frac{n !}{k ! ( n - k )!}$ . $(- 1)^{k + 1}$ produces ::: $+ 1$ for odd $k$ (add) and $- 1$ for even $k$ (subtract). $P (A) = ∣ A ∣/∣ S ∣$ tells us ::: the fraction of the universe box that $A$ covers — probability from counting. Net count of an element in $m$ sets is ::: exactly $1$ , because $\sum_{k = 1}^{m} (- 1)^{k + 1} (k m) = 1$ .

Connections

Set Theory & Venn Diagrams — where circles, union and intersection come from
Counting Principles & Combinatorics — the $(k n)$ and disjoint-addition machinery
Probability Axioms — additivity is the disjoint special case
Derangements & Permutations — a payoff that reuses $(k n)$ and factorials
Binomial Theorem — the identity $(1 - 1)^{m} = 0$ that forces the alternating signs
Bonferroni Inequalities — what happens if you stop the alternating sum early