Question

Prove the set of subsets of a finite set has cardinality 2^x

Answer 1

Let's take the simple case of a set with four elements: the letters a-d

$\{a,b,c,d\}$

Two subsets that this - and any other - set contains are the empty set ∅ and the set itself. Now, if we wanted, we could construct the rest of the subsets by picking elements from the original set at random - {a, b, c}, {a, c}, and {c, d} to name a few - but this process is incredibly inefficient, and there's a good chance you'll miss a few subsets this way.

There's a part in that last paragraph that's extremely important: we're picking elements from the original set to put in our subsets, and this selection process boils down to a single yes or no question: do we want to add this element to our subset? This is where that 2 emerges in the original question - we're asking a question with 2 possible outcomes, and we're asking it x times, where x is the number of elements in our set.

For instance, with the set {a, b, c, d}, constructing subsets consists of four questions:

- Should we add a to the subset? Yes/No

- Should we add b? Yes/No

- Should we add c? Yes/No

- Should we add d? Yes/No

The space of possible outcomes, and consequently possible subsets, these questions produce is the same as the space of possible outcomes for 4 yes-or-no questions: $2^4=16$