Show that the set of all finite subsets of $\mathbb{N}$ is countable.

Question

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?

Answer 1

Consider an enumeration of the (positive) prime numbers by $n\mapsto p_n$. Then if you're given the set $\{n_1,...,n_k\}$, map that to $$p_{n_1}\cdots p_{n_k}.$$ For example, if we've enumerated the primes increasingly ($p_1=2$, $p_2=3$, and so on), then $$\{1,3,4\}\mapsto 70=2\cdot 5\cdot 7=p_1\cdot p_3\cdot p_4,$$ and $$\{1,3\}\mapsto 10=2\cdot 5=p_1\cdot p_3.$$

You'll need the fact that there are countably infinitely many prime numbers, and uniqueness of prime factorization. From there, it shouldn't be hard to prove this is an injection from the set of finite subsets of $\Bbb N$ into $\Bbb N$, so there are at most countably many such subsets. To show that there are at least (and so exactly) countably many finite subsets of $\Bbb N$, you need only find an injection from $\Bbb N$ into the set of finite subsets of $\Bbb N$, which should be easy.

Added: The described map "should" send $\emptyset$ to $1,$ the "empty product." Even if this doesn't make sense to you, though, you can define the function for non-empty finite subsets, and from there, use the easy-to-prove fact that the union of a countably infinite set and a singleton--in this case, $\{\emptyset\}$--is countably infinite.

Answer 2

Let $p_1,p_2,\ldots$ the sequence of primes. Then map each finite subset $\{a_1,\ldots,a_n\} \subset \mathbb N$ to $p_1^{a_1}\cdots p_n^{a_n}$ where $a_1 < \ldots < a_n$. This gives an injective map from the set of finite subsets of $\mathbb N$ to $\mathbb N$.

Alternatively, notice that for every $s$ there are only finitely many finite subsets of $\mathbb N$ whose sum is $\leq s$. Let $A_s$ be the set of those subsets, then $\mathbb N = \bigcup_{s} A_s$ is a countable union of finite sets, hence countable.

Answer 3

Alternatively, just use base $2$, so send $\{a_1,...,a_n\}$ to $2^{a_1}+\cdots+2^{a_n}$. (Assuming your $\mathbb N$ includes $0$, this is $1-1$ and onto.)

Answer 4

The other answers give some sort of formula, like you were trying to do. But, the simplest way to see that the set of all finite subsets of $\mathbb{N}$ is countable is probably the following.

If you can list out the elements of a set, with one coming first, then the next, and so on, then that shows the set is countable. There is an easy pattern to see here. Just start out with the least elements.

$$\emptyset, \{1\}, \{2\}, \{1, 2\}, \{3\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}, \{4\}, \ldots$$

In other words, first comes $\{1\}$, then comes $\{2\}$. Each time you introduce a new integer, $n$, list all the subsets of $[n] = \{1, 2, \ldots, n\}$ that contain $n$ (the ones that don't contain $n$ have already showed up). Therefore, all subsets of $[n]$ show up in the first $2^{n}$ elements of this sequence.

Answer 5

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.

Answer 6

I'm surprised nobody else has said this, so I worry that I've missed the point of the question. But I would argue as follows: Let $N_i$ be the family of all subsets of $\Bbb N$ with exactly $i$ elements. $N_0$ is finite, and $N_1$ is countable. $N_2$ is countable also, since it's a subset of $\Bbb N\times \Bbb N$. There's an easy induction argument that $N_i$ is countable for all $i>0$, since it's contained in the product $\Bbb N\times N_{i-1}$ of two countable sets.

Then, since the set you want, $\bigcup N_i$, is a countable union of countable sets, it is countable.