Counting the Number of Subsets of a Finite Set

Consider the finite $3$-element set $A = \{ x_1, x_2, x_3 \}$. Suppose that we want to determine the total number of distinct subsets that can be formed from $A$. It's not too difficult to list these sets, and it turns out that the subsets$\emptyset, \{ x_1 \}, \{ x_2 \}, \{ x_3 \}, \{ x_1, x_2 \}, \{ x_1, x_3 \}, \{ x_2, x_3 \}, \{ x_1, x_2, x_3 \}$ are the only subsets of $A$ and that there are exactly $8$ of them.

In general, it might be convenient to know the total number of distinct subsets that can be formed from a finite $n$-element set $A$ such as:

(1)

\begin{align} \quad A = \{ x_1, x_2, ..., x_n \} \end{align}

The following theorem uses The Binomial Theorem to show us that for any finite $n$-element set there are exactly $2^n$ distinct subsets of $A$.

Theorem 1: If $A$ is a finite $n$-element then there are exactly $2^n$ distinct subsets of $A$.

• Proof: Let $A = \{ x_1, x_2, ..., x_n \}$ be an $n$-element set. Then the total number of subsets containing zero elements is $\binom{n}{0}$, the total number of subsets containing one element is $\binom{n}{1}$, …, and the total number of subsets containing $n$ elements is $\binom{n}{n}$. By the addition principle we see that:

(2)

\begin{align} \quad \mathrm{total \: number \: of \: subsets \: of} \: A = \sum_{k=0}^{n} \binom{n}{k} \end{align}

• Recall that for all $x, y \in \mathbb{R}$ and $n \in \{ 0, 1, 2, ... \}$ we have that the binomial expansion of $(x + y)^n$ is given by the formula:

(3)

\begin{align} \quad (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^y y^{n-k} \end{align}

• Setting $x = y = 1$ will give us:

(4)

\begin{align} \quad 2^n = \sum_{k=0}^{n} \binom{n}{k} \end{align}

• Therefore we have that:

(5)

\begin{align} \quad \mathrm{total \: number \: of \: subsets \: of} \: A = 2^n \quad \blacksquare \end{align}

For example, consider the five element set $D = \{ v, w, x, y, z \}$. From Theorem 1 above we see that there are $2^5 = 32$ distinct subsets of $D$ (try to list them all).