Let's prove that, if a set has size \(n\), then that same set has exactly \(2^n\) subsets.

|S| = n implies that |P(S)| = 2^n

Twitter proof

Take a set of size \(n\). For any of its subsets, we can label items with \(0\)/\(1\) depending on whether or not the item is in the subset or not, and to any such labelling corresponds a single subset. There are \(2^n\) such labellings, hence \(2^n\) subsets.

Previous Post Next Post

Blog Comments powered by Disqus.