Prove by method of induction that if A has n elements, then |P(A)|=2^n
Answers
Answer:
The proof is pretty simple. Recall what the power set P(A) is: the set of all subsets from A . Now the base case is A=∅ , so A has 0 elements, while P(A) has 1 element: A . And indeed 20=1 . So let us assume that if A has k elements than length( P(A))=2k .So we put a new element α in A we can make 2 new subsets from all the existing ones: 1 where α is part of the subset and one where it is left unchanged. So now length(P(A))=2k×2=2k+1 and just for comparison A has k+1 elements. So q.e.d.
An other way to reason about it: if A has n elements than you could index all elements from 0 to n−1 and write binary strings with length n to represent possible subsets indexed the same way as A . If bit i is 1 this means element i is in the subset. So it is easy to see that every subset can be represented by a binary number from 0 (empty set) to 2n−1 ( A itself) and it is known that in base b you can make bn digits strings with a maximum length of n (and a minimum length of 1 ).
