Prove that the set of all finite subsets of natural numbers \(\mathbb{N}\) is countable. Then prove that the set of all subsets of natural numbers is not countable.
How many subsets are there of \(\{1,2,...,n\}\) (the integers from \(1\) to \(n\) inclusive) containing no consecutive digits? That is, we do count \(\{1,3,6,8\}\) but do not count \(\{1,3,6,7\}\).