█ Q1. If A is a finite set having n elements, prove that A has exactly 2n distinct subsets.
▶ Solution. Apply induction on n.
If |A| = 1, then A has exactly two subsets namely ϕ and A. So, the claim is true for n = 1.
For any set having exactly n − 1 elements, the number of subsets is 2n − 1.
Let now A = {a1, a2, · · · , an} be a set with |A| = n.
Any subset X of A is either contained in B = {a1, · · · , an − 1} or an ∈ X.
By induction hypothesis, there are exactly 2n− 1 subsets of A contained in B.
Any other subset X of A which is not contained in B is of the form X = {an} ∪ Y where Y is a subset of B. Their number is therefore equal to the number of subsets of B, i.e., 2n− 1.
Then the number of all subsets of A is 2n− 1 + 2n− 1 = 2n. ▲