Question

use product rule to show that the number of different subsets of a finite set S is 2^|S|

Answer 1

I'm not familiar with the product rule, at least not by name, but one way to do it is by applying the binomial theorem.

For a set \(S\) with \(|S|\) elements, you would count how many ways there are of choosing a certain number of elements from the set.

For example, how many ways can you choose zero or no elements? One - take the empty subset, i.e. \(\dbinom{|S|}0=1\).

How many ways can you choose one element? \(|S|\) - take one element from \(|S|\) elements, and you have \(\dbinom{|S|}{1}=|S|\).

And so on, up to how many ways can you choose all the elements? One - take the set \(S\), i.e. \(\dbinom{|S|}{|S|}=1\).

Then you sum all these together:
\[\binom{|S|}0+\binom{|S|}1+\cdots+\binom{|S|}{|S|}=\sum_{n=0}^{|S|}\binom{|S|}n\]