Simple Propositions & Inclusion–Exclusion

May 2026 · 16 min read

The three axioms are sparse on purpose — they say nothing about $P(\emptyset)$, complements, or unions of overlapping events. In this post we crank out the small list of consequences that every probability problem afterward will use. The whole catalogue derives from finite additivity (Axiom 3) plus a couple of set-theoretic decompositions.

Proposition 1. $P(\emptyset) = 0$

Why it works. $S$ and $\emptyset$ are disjoint, and $S \cup \emptyset = S$. By finite additivity

$P(S) = P(S \cup \emptyset) = P(S) + P(\emptyset).$

Subtracting $P(S)$ from both sides gives $P(\emptyset) = 0$.

Proposition 2. Complement Rule. $P(A^c) = 1 - P(A)$

Why it works. $A$ and $A^c$ are disjoint with $A \cup A^c = S$. By Axioms 2 and 3,

$1 = P(S) = P(A) + P(A^c).$

Rearrange.

Proposition 3. Monotonicity. If $A \subseteq B$ then $P(A) \le P(B)$

Why it works. Decompose $B$ into the part inside $A$ and the part outside:

$B = A \cup (B \cap A^c)$, and these two pieces are disjoint.

By finite additivity, $P(B) = P(A) + P(B \cap A^c)$. The second term is $\ge 0$ by Axiom 1, so $P(A) \le P(B)$. The same line gives the useful identity

Proposition 4. Addition Rule for Two Events

This is the workhorse formula. The intuition: $P(A) + P(B)$ counts everything in $A \cap B$ twice, so we subtract one copy.

Why It Works

Decompose $A \cup B$ into three disjoint pieces:

• $A \cap B^c$ (in $A$ only),
• $A \cap B$ (in both),
• $A^c \cap B$ (in $B$ only).

By finite additivity,

$P(A \cup B) = P(A \cap B^c) + P(A \cap B) + P(A^c \cap B).$

Now express $P(A)$ and $P(B)$ themselves using the same disjoint decomposition:

$P(A) = P(A \cap B^c) + P(A \cap B), \qquad P(B) = P(A^c \cap B) + P(A \cap B).$

Adding these two and subtracting one copy of $P(A \cap B)$ matches our expression for $P(A \cup B)$ exactly.

Visual: The Inclusion–Exclusion Bookkeeping

Step through the addition rule by shading $A$, then $B$, then watching the double-counted overlap, then subtracting one copy of it.

Proposition 5. Three Events

Same idea: each region of the three-circle Venn diagram should be counted exactly once. Start by adding $P(A) + P(B) + P(C)$. Now:

• The pairwise overlaps $AB$, $AC$, $BC$ have each been counted twice, so subtract one copy of each.
• That accidentally over-corrects the triple overlap $ABC$: it was counted three times originally, then subtracted three times in the pairwise step, leaving zero. Add it back once.

Proposition 6. General Inclusion–Exclusion

For any $n$ events $A_1, \ldots, A_n$,

Or compactly,

$\displaystyle P\!\left(\bigcup_{i=1}^{n} A_i\right) = \sum_{k=1}^{n} (-1)^{k+1} \!\!\!\sum_{1 \le i_1 \lt \cdots \lt i_k \le n} \!\!\! P(A_{i_1} A_{i_2} \cdots A_{i_k}).$

Proof Sketch (Indicator Trick)

For any outcome $s$, count it on each side. Let $r$ be the number of events $A_i$ that contain $s$. The left side counts $s$ once if $r \ge 1$. On the right side, $s$ appears in the $k$-fold intersection sum with sign $(-1)^{k+1}$ for each choice of $k$ events out of the $r$ that contain it, contributing $(-1)^{k+1} \binom{r}{k}$ for each $k$. Summing,

$\displaystyle \sum_{k=1}^{r} (-1)^{k+1} \binom{r}{k} = -\sum_{k=1}^{r} (-1)^{k} \binom{r}{k} = -\!\left[\sum_{k=0}^{r}(-1)^k \binom{r}{k} - 1\right] = -\bigl[(1-1)^r - 1\bigr] = 1$

(using the binomial expansion of $(1 - 1)^r = 0$ for $r \ge 1$). So both sides agree on every outcome, hence on every event.

Proposition 7. Bonferroni Inequalities

Truncating the inclusion–exclusion sum gives upper and lower bounds:

• Bonferroni upper bound (union bound): $P\!\left(\bigcup_i A_i\right) \le \sum_i P(A_i)$.
• Bonferroni lower bound: $P\!\left(\bigcup_i A_i\right) \ge \sum_i P(A_i) - \sum_{i \lt j} P(A_iA_j)$.

The union bound (also called Boole's inequality) is constantly used in machine learning and CS theory: when you have many "bad events", you bound the probability that any of them happens by summing their probabilities. It is loose but free.

Worked Example: At Least One of Three

A student tries three problems independently with success probabilities $p_1 = 0.6$, $p_2 = 0.5$, $p_3 = 0.4$. Find the probability she solves at least one.

Hard way (inclusion–exclusion). Need pairwise and triple intersection probabilities; with independence those are $p_1 p_2$, $p_1 p_3$, $p_2 p_3$, $p_1 p_2 p_3$. Slogging through gives the right answer but is error-prone.

Easy way (complement). "Solves none" = all three fail, with probability $(1-p_1)(1-p_2)(1-p_3) = 0.4 \cdot 0.5 \cdot 0.6 = 0.12$. So $P(\text{at least one}) = 1 - 0.12 = 0.88$.

This is exactly the complement rule (Proposition 2) plus independence. It generalises: $P(\bigcup_i A_i) = 1 - \prod_i (1 - p_i)$ when the $A_i$ are independent.

Worked Example: The Matching Problem

$n$ people drop their hats into a basket; each picks one at random. What is the probability that at least one person gets their own hat back?

Let $A_i$ = "person $i$ gets their own hat". By symmetry $P(A_i) = 1/n$. For distinct $i, j$, $P(A_i A_j) = \frac{(n-2)!}{n!} = \frac{1}{n(n-1)}$, and in general for $k$ specified people, $P(A_{i_1} \cdots A_{i_k}) = \frac{(n-k)!}{n!}$.

Apply inclusion–exclusion. The $k$-th sum has $\binom{n}{k}$ terms each equal to $(n-k)!/n!$, so it equals $1/k!$. Therefore

$\displaystyle P\!\left(\bigcup_{i=1}^n A_i\right) = \sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!} = 1 - \sum_{k=0}^{n} \frac{(-1)^k}{k!}.$

As $n \to \infty$ this tends to $1 - e^{-1} \approx 0.632$. The probability of at least one match converges to a constant, and the probability of no match converges to $1/e$. This is one of the prettiest results in elementary probability and falls straight out of inclusion–exclusion.

Common Mistakes

• Applying $P(A \cup B) = P(A) + P(B)$ when $A$ and $B$ overlap. Always check disjointness or pay the $-P(A \cap B)$ tax.
• Forgetting the alternating signs in inclusion–exclusion. There's an easy memory aid: with $n$ events, you have $2^n - 1$ non-empty subsets to sum over, alternating $+, -, +, -, \ldots$ by subset size.
• Confusing the matching problem's $1/e$ with the probability that exactly one person gets a match. We computed “at least one”.
• Using the union bound in problems with very correlated events; the bound becomes meaningless when individual probabilities are large.

Practice

1. Prove $P(A) = P(A \cap B) + P(A \cap B^c)$ from the axioms.
2. Given $P(A) = 0.7$, $P(B) = 0.6$, $P(A \cap B) = 0.5$, compute $P(A \cup B)$, $P(A \cap B^c)$, $P(A^c \cap B^c)$.
3. Prove the union bound $P\!\left(\bigcup_i A_i\right) \le \sum_i P(A_i)$ directly from finite additivity by writing the union as a disjoint union $A_1 \cup (A_2 \setminus A_1) \cup (A_3 \setminus (A_1 \cup A_2)) \cup \cdots$.
4. $10$ people drop their hats into a basket and pick one at random. What is the probability that exactly $k$ people get their own hat? (Hint: combine the matching computation with combinatorial choice.)
5. Three students independently solve a problem with probabilities $0.5, 0.4, 0.3$. Compute the probability that exactly two solve it using inclusion–exclusion on the pairwise events.
6. Show that for any events $A, B$, $P(A \cap B) \ge P(A) + P(B) - 1$ (this is sometimes called the trivial Fréchet inequality).