Sets Flashcards
1
Q
Prove:
Number of subsets of a set of n elements is 2n.
A
This is true for n=0 because ∅ has exactly one subset, namely ∅ itself.
Now assume that the claim is true for sets with n many elements. Given a set Y with n+1 many elements, we can write Y=X ∪ {p} where X is a set with n many elements and p ∉ X. There are 2n many subsets A ⊂ X, and each subset A ⊂ X gives rise to two subsets of Y, namely A ∪ {p} and A itself. Moreover, every subset of Y arises in this manner. Therefore the number of subsets of Y is equal to 2n⋅2, which in turn is equal to 2n+1.
