Prove that the number of subsets of a set S is 2n if S nSol

Prove that the number of subsets of a set S is 2^n if |S| = n.

Solution

Hint: There is also a proof through mathematical inducation! which you can try for yourself.

But here\' a simple and logical explanation /proof for the same:

Lets say you want to choose a subset.

For each element, you have two choices:

1. You put it in your subset,
2. or you don\'t;

and these choices are all independent.

This works also for the empty set. An empty set has exactly one subset, namely the empty set. And the fact that 2^0=1 reflects the fact that there is only one way to pick no elements at all!