/sci/ - Science & Math

Hello friends. Today I have proved that the power set of any set with N elements contains 2^N elements. I have not seen a proof for it before so I did it all from scratch, other than knowing the end result to look for!

First, we need a lemma. The lemma is pic related which shows that the nth layer of the magic pyramid (counting from layer 0), has a sum of terms equal to 2^n.

Now, we show that for a set of size N, it has Ki subsets of size i, for each i in layer n of the magic pyramid, giving it 2^n subsets. We can show this recursively, starting from layer n = 1, which can easily be checked that it holds. For a set of N = 2, we see that it contains the empty set, so it has 1 subset of size 0, agreeing with the magic pyramid for K0.
Next we prove that for any set, its subsets of size i>0 equal the number of subsets of size i>0 in any set size N-1, plus the number of subsets of size i-1 in set N-1. Take a given set, and remove an element from it. All the subsets of size i in the lesser set are also in the greater set. Also, all Ki-1 subsets of size i-1 in the lesser set can be united with the element removed from the greater set, creating Ki-1 additional subsets of size i. We must show that these are the only subsets of size i in the greater set. This can be seen by the fact that if a subset is solely made of elements from the lesser set, it is in the former group, and if it contains any elements outside the lesser set, it can only be one element (since that is the difference of sets), leaving the other i-1 in the lesser set. So, if a subset of size i or i-1 is in lesser, a corresponding set is in greater, and if it is in greater, it is in or corresponds to from a subset in lesser (with no overlap), leading to Ki on the new layer being sum of Ki-1 and Ki on the preceding layer of the pyramid.