Q:

A set with $n$ elements has $2^n$ subsets; follows from the multiplication rule?

My textbook says that the following theorem follows from the multiplication rule:

A set with $n$ elements has $2^n$ subsets, including the empty set $\emptyset$ and the set itself.

The multiplication rule that I am alluding to is as follows:

Consider a compound experiment consisting of two sub-experiments, Experiment A and Experiment B. Suppose that Experiment A has $a$ possible outcomes. Then the compound experiment has $ab$ possible outcomes.

How does the first theorem follow from the multiplication rule, as the author suggests?
I would greatly appreciate it if people could please take the time to clarify this.

A:

Suppose we are constructing a subset of $\{a_i\}_{i=1}^n$. Let experiment $1$ be to test inclusion of $a_1$ into the subset. There are $2$ possible outcomes: the element is included, or not included. Let experiment $2$ test inclusion of $a_2$ into the subset. There are $2$ possible outcomes, and so on, giving a factor of $2$ for each $i$ between $1$ and $n$. Thus, using the Multiplication Principle, the total number of possible subsets is $2^n$.

