Michael Sipser Edition 3 Exercise 0 Question 5 (Page No. 26)

Question

If C is a set with c elements, how many elements are in the power set of C? Explain your answer.

Answer 1

The power set will have $2^c$ elements.
This is because while generating the powet set, we have two choices for each element in the original set.
Hence, $\underbrace{2 \times 2 \times \dots 2}_{\text{c times }} = 2^c$.

Answer 2

One well know way is already there in answer. Here is another way.

The number of subsets with k elements in the power set of a set with n elements is given by the number of combinations, C(n, k), also called binomial coefficients.

For example, the power set of a set with three elements, has:

• C(3, 0) = 1 subset with 0 elements (the empty subset),
• C(3, 1) = 3 subsets with 1 element (the singleton subsets),
• C(3, 2) = 3 subsets with 2 elements (the complements of the singleton subsets),
• C(3, 3) = 1 subset with 3 elements (the original set itself).

Using this relationship we can compute  using the formula:

 

 

Therefore, one can deduce the following identity, assuming ${\textstyle |S|=n}$​​​​​​​

 

 

 

Source: https://en.wikipedia.org/wiki/Power_set#Relation_to_binomial_theorem