Counting for Sets

Section 9.1 Counting for Sets

Subsection 9.1.1 The Addition Rule

Theorem 9.1.1.

If there are \(n_1\) ways to make choice 1, and \(n_2\) ways to make choice 2, then the number of ways to make one of the two choices, but not both of them, is \(n_1 + n_2\text{.}\)

In the language of set theory,

Theorem 9.1.2.

Let \(A, B\) be finite sets, which are disjoint. Then,

\begin{equation*} \boxed{n(A \cup B) = n(A) + n(B)} \end{equation*}

More generally,

Theorem 9.1.3.

Let there be \(k\) choices, with \(n_1\) ways to make choice 1, \(n_1\) ways to make choice 2, etc. up to \(n_k\) ways to make choice \(k\) (in general for choice \(i\text{,}\) there are \(n_i\) ways). Then, the number of ways to make exactly one of the \(k\) choices is,

\begin{equation*} n_1 + n_2 + \dots + n_k \end{equation*}

In the language of set theory,

Theorem 9.1.4. Addition rule.

Let \(A_1, \dots, A_n\) be finite sets, which are pairwise disjoint. Then,

\begin{equation*} \boxed{n(A_1 \cup \cdots \cup A_n) = n(A_1) + n(A_2) + \dots + n(A_n)} \end{equation*}

Similar to the FCP, the addition rule can be thought of as axiom.

Subsection 9.1.2 The Difference Rule

Theorem 9.1.5.

Let \(A, B\) be finite sets, \(B \subseteq A\text{.}\) Then,

\begin{equation*} \boxed{n(A \setminus B) = n(A) - n(B)} \end{equation*}

Proof.

If \(B \subseteq A\text{,}\) then \(B\) and \(A \setminus B\) are disjoint sets, and \(B \cup (A \setminus B) = A\text{.}\) Thus, \(B\) and \(A \setminus B\) partition \(A\text{,}\) so,

\begin{equation*} n(B) + n(A \setminus B) = n(A) \end{equation*}

Then, subtracting \(n(B)\) from both sides gives the result.

Subsection 9.1.3 The Inclusion-Exclusion Principle

Recall that for disjoint sets, the addition rule specifies the number of elements in the union of the sets. Next, consider if the sets are overlapping. Consider a Venn diagram with two sets, \(A\) and \(B\text{.}\)

When \(n(A)\) and \(n(B)\) are added, their intersection is counted twice. Then, for the correct number of elements, we need to subtract \(n(A \cap B)\text{.}\) Thus,

Theorem 9.1.6. Inclusion-exclusion principle for two sets.

Let \(A, B\) be finite sets. Then,

\begin{equation*} \boxed{n(A \cup B) = n(A) + n(B) - n(A \cap B)} \end{equation*}

For three sets \(A, B, C\text{,}\) adding \(n(A)\text{,}\) \(n(B)\text{,}\) and \(n(C)\) counts the intersections \(n(A \cap B)\text{,}\) \(n(A \cap C)\text{,}\) and \(n(B \cap C)\) each twice. Then, to compensate for this, we subtract off each of these three intersections. However, then this again overcompensates by not counting the intersection \(n(A \cap B \cap C)\) at all. Then, finally, we add back \(n(A \cap B \cap C)\text{.}\) In summary,

Theorem 9.1.7.

Let \(A, B, C\) be finite sets. Then,

\begin{equation*} \boxed{n(A \cup B \cup C) = n(A) + n(B) + n(C) - n(A \cap B) - n(A \cap C) - n(B \cap C) + n(A \cap B \cap C)} \end{equation*}

In fact, there is a more general and mathematically advanced formula for the cardinality of the union of \(n\) sets, which relies on generalizing this reasoning.