Show that the set of all finite subsets of $\mathbb{N}$ is countable.
I'm not sure how to do this problem. I keep trying to think of an explicit formula for 1-1 correspondence like adding all the elements in each subset and sending that sum to itself in the natural numbers, but that wouldn't be 1-1 because, for example, the set {1,2,3} would send to 6 and so would the set {2,4}. Multiplying all the elements in each subset and sending that product to itself in the natural numbers wouldn't work either since, for example, {2,3} would send to 5 and so would the set {1,5}. Any ideas?
Best Answer
Define three new digits: $$\begin{align} \{ &= 10 \\ \} &= 11\\ , &= 12 \end{align}$$ Any finite subset of $\mathbb{N}$ can be written in terms of $0,1,\cdots,9$ and these three characters, and so any expression of a subset of $\mathbb{N}$ is just an integer written base-$13$. For instance, $$\{1,2\} = 10 \cdot 13^4 + 1 \cdot 13^3 + 12 \cdot 13^2 + 2 \cdot 13^1 + 11 \cdot 13^0 = 289873$$
So for each finite $S \subseteq \mathbb{N}$, take the least $n_S \in \mathbb{N}$ whose base-$13$ expansion gives an expression for $S$. This defines an injection into $\mathbb{N}$.
More generally, any set whose elements can be written as finite strings from some finite (or, in fact, countable) alphabet, is countable.