Is the collection of finite subsets of $\mathbb{Z}$ countable? The collection of all subsets of $\mathbb{Z}$ is uncountable, due to Cantor's theorem
But how can I prove that the collection of all finite subsets of $\mathbb{Z}$ is countable?
 A: Hint: Show that the collection of subsets of $\mathbb{Z}$ of a fixed finite cardinality is countable. Then think about countable unions of such collections.
A: There is a nice bijection between $\mathbb{Z}$ and the set $\mathbb{N}$ of nonnegative integers. From this we can get a bijection between the set of finite subsets of $\mathbb{Z}$ and the set of finite subsets of $\mathbb{N}$. Thus it is enough to show that the set of finite subsets of $\mathbb{N}$ is countable. 
For any finite subset $A$ of $\mathbb{N}$, let $a_i=1$ if $i\in A$, and let $a_i=0$ otherwise. Let 
$$\psi(A)=\sum_{i=0}^\infty 2^i a_i$$
(note that the sum is effectively a finite sum). The map $\psi$ is a bijection from the set of finite subsets of $\mathbb{N}$ to $\mathbb{N}$. 
We are using the integer with binary representation $\dots a_na_{n-1}\dots a_2a_1a_0$ to represent $A$.
A: Every expression for a finite subset $S \subseteq \mathbb{Z}$ is a base-$14$ integer expression, using four new digits:
$${\{} = 10, \quad {\}} = 11, \quad {,} = 12, \quad {-} = 13$$
so for example
$$\begin{align}
\{1,-2,9,51\} &= 11+1\cdot14+5\cdot14^2+12\cdot14^3+9\cdot14^4+12\cdot14^5+2\cdot14^6\\
& \qquad +13\cdot14^7+12\cdot14^8+14^9+10\cdot14^{10}\\
&= 2932309333405
\end{align}$$
You can thus define an injection $\mathcal{P}_{\text{fin}}(\mathbb{Z}) \to \mathbb{N}$ by mapping a finite subset $S \subseteq \mathbb{Z}$ to the least integer representing $S$ in base $14$ with digits defined as above.
A: Notice the set of all finite subsets of $\mathbb{Z}$ can be rewritten as a countable union.
$$\Big\{\; A \subseteq \mathbb{Z}\;:\;|A| < \infty \;\Big\}
= \bigcup_{n=0}^\infty \Big\{\;A \subseteq \mathbb{Z}\;:\; \max\big\{\; |x| \;:\; x \in A \;\big\}\le n\;\Big\}
$$
Now the sets of subsets on R.H.S have cardinality $2^{2n+1}$ for each $n$, the set of all finite subsets on LHS is at most countable infinite.
