Showing that the set of all finite subsets of $\mathbb{N}$ is a countable set. I'm working through Understanding Analysis by Abbott and was wondering about the correctness of my solution to a problem in section 1.4. Exercise 1.4.10 asks:


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


So my idea for a solution is to use induction. The base case is simple, with each element of $\mathbb{N}$ mapping to a singleton of itself. Clearly we have a bijection and thus all the subsets of size 1 are countable. From here we assume that the set of all finite subsets of $\mathbb{N}$ of size $k-1$ is a countable set. Let $\{B_1, B_2, B_3, B_4, \dots \}$ be an enumeration of the subsets of size $k-1$ of $\mathbb{N}$. For a given $i \in \mathbb{N}$, the family $\{B_k \cup \{i\} : k \in \mathbb{N}\}$ is similarly countable. The family on subsets of $\mathbb{N}$ of size $k$ can then be written as the union

$$\bigcup_{i=1}^\infty{\left\{B_k \cup \{i\} : k \in \mathbb{N}\right\}}.$$

This is a countable union of countable families of sets and is thus countable. So, the set of all subsets of $\mathbb{N}$ of size $k$ is countable and thus by induction this statement holds true for all $n \in \mathbb{N}$.

Now let $A_i$ be the family of subsets of $\mathbb{N}$ of size $i$. By above each of these families is countable. Thus

$$\bigcup_{i=1}^\infty{A_i}$$

is the set of all finite subsets of $\mathbb{N}$ and since it is a countable union of countable families of sets our result follows.

Is this a valid proof? The only thing I'm a little unsure of is writing the family of subsets of size $k$ as I do in that first union. Any other comments are welcome as well.
With the minor correction made in your comment (the family of $k$-subsets is contained in the union you wrote; it's not equal to that union, because the union contains some $(k-1)$-subsets as well), your proof is correct.  I would probably write it in a way that makes no use of enumerations of the countable sets involved... other answers show that there are very clean ways to prove the countability of $\cal{P}(\mathbb{N})$ specifically, so it's nice for you to have a slightly more abstract approach:


  Thm: If $X$ is a countable set, then so is ${\cal{P}}(X)$.


Proof (OP):

Let $A_k(X)$ be the set of $k$-subsets of $X$.   We will show that $A_k(X)$ is countable for each $k$, by induction.  Clearly $A_0(X)=\{\emptyset\}$ is countable.  For $k\ge 1$, assume $A_{k-1}(X)$ is countable.  We have
$$
A_{k}(X)=\bigcup_{x\in X}\bigcup_{Y\in A_{k-1}(X) : x\notin Y}\{Y\cup\{x\}\}.
$$
This is a countable union (since $X$ is countable) of countable unions (since $A_{k-1}(X)$ is countable by hypothesis) of finite sets; hence it is a countable union of countable sets; hence it is countable.  By induction, then, $A_k(X)$ is countable for all $k$.  We conclude that $${\cal{P}}(X)=\bigcup_{k=0}^{\infty}A_k(X)$$
is also a countable union of countable sets, and hence countable.
$\;\square$
Let $n \in \mathbb{N}$ and $b_m b_{m-1}\ldots b_2 b_1 b_0$ be its expansion in binary. There are technically an infinite number of $0$'s to the left of the expansion, so it makes sense to talk about bits $b_r$, for $r &gt; m$.

The binary expansion of a number provides a natural way to talk about the subsets of $\mathbb{N}$. Each bit is either $1$ or $0$, and each element of $\mathbb{N}$ is either in or not in a given subset. 

For $n$ as described above with a binary expansion $b_m b_{m-1}\ldots b_2 b_1 b_0$, construct the subset of $\mathbb{N}$ specified by $\{a \in \mathbb{N} \vert b_{a-1} = 1\}$. This subset is finite since $n$ is finite, and therefore has a finite binary expansion. Moreover, since binary expansions are unique, no two natural numbers can specify the same subset of $\mathbb{N}$. Every subset of $\mathbb{N}$ can be associated with a unique binary expansion (and consequently, a unique natural number), showing that this construction is bijective.

Since $\mathbb{N}$ is countable and the set of finite subsets is bijective to $\mathbb{N}$, this set is also countable.