Use induction to prove that every set of n elements has 2ⁿ distinct subsets, for all n ? 0.

Hint for the inductive case: fix some element of the set and consider whether it belongs to the subset or not. In either case, reduce to the inductive hypothesis.