Counting principles

This formalizes the everyday habit of counting each disjoint case separately and adding: it is valid precisely because disjointness prevents any outcome from being counted twice.

Step 1 (base case $k=2$): suppose $A_1$ and $A_2$ are disjoint, so $A_1 \cap A_2 = \emptyset$. Every element of $A_1 \cup A_2$ lies in $A_1$ or in $A_2$, and disjointness rules out lying in both. Splitting $A_1 \cup A_2$ into the two disjoint pieces $A_1$ and $A_2$ and counting each piece once therefore gives $|A_1 \cup A_2| = |A_1| + |A_2|$.

Step 2 (induction on $k$): assume the formula already holds for any $k-1$ pairwise disjoint sets, so $|A_1 \cup \cdots \cup A_{k-1}| = |A_1| + \cdots + |A_{k-1}|$. Set $B = A_1 \cup \cdots \cup A_{k-1}$. Because $A_k$ is disjoint from every $A_i$ with $i < k$, it is also disjoint from their union $B$. Applying the base case to $B$ and $A_k$ gives $|B \cup A_k| = |B| + |A_k|$.

Step 3 (combine): substituting the inductive hypothesis for $|B|$ into the last equality gives $|A_1 \cup \cdots \cup A_k| = |A_1| + \cdots + |A_{k-1}| + |A_k|$, which is exactly the addition rule for $k$ sets. Since the base case $k=2$ holds and each step from $k-1$ to $k$ preserves the formula, it holds for every $k \geq 2$ by induction.

Because each step's number of choices does not depend on earlier steps, every combination of choices is a distinct legal outcome, and the count of combinations multiplies exactly like counting cells in a rectangular grid.

Step 1 (base case $k=1$): with a single step there are trivially $N_1 = n_1$ ways, matching the formula for $k=1$.

Step 2 (base case $k=2$): for each of the $n_1$ ways to perform step 1, step 2 can still be done in $n_2$ ways, since its count does not depend on step 1's outcome. This splits all pairs of choices into $n_1$ disjoint groups of size $n_2$ (one group per outcome of step 1), so the addition rule gives a total of $n_2$ added to itself $n_1$ times, i.e. $N_2 = n_1 \cdot n_2$.

Step 3 (induction on $k$): assume the formula holds for $k-1$ steps, so the first $k-1$ steps together admit $N_{k-1}$ outcomes. Treat those $k-1$ steps as one combined "super-step" with $N_{k-1}$ outcomes, and step $k$ as a second, independent step with $n_k$ outcomes (its count still does not depend on earlier choices). Applying the two-step base case to this pair gives $N_k = N_{k-1} \cdot n_k$, which is $N_k = n_1 \cdot n_2 \cdots n_k$. By induction the formula holds for every $k$.