Let's take the simple case of a set with four elements: the letters a-d
[tex] \{a,b,c,d\} [/tex]
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: [tex] 2^4=16 [/tex]
