Is the collection of finite subsets of $\mathbb{Z}$ countable?

Solution 1:

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.

Solution 2:

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$.