Set of Finitely Supported Functions on Integers is Countable

Theorem

Let $\SS$ be the set of functions $f : \Z \to \Z$ for which there exists $N \in \N$ such that:

$\map f n = 0$ for all $n \in \Z$ with $\size n > N$.

Then $\SS$ is countable.

Proof

Let $\sequence {p_n}_{n \mathop \in \N}$ be an enumeration of the prime numbers.

For each $f \in \SS$ let $N_f \in \N$ be least such that:

$\map f n = 0$ for all $n \in \Z$ with $\size n > N_f$.

Then for each $f \in \SS$, define $\map \phi f$ by:

$\ds \map \phi f = 2^{\map f 0} \prod_{j \mathop = 1}^{N_f} p_{2 j + 1}^{\map f j} \prod_{j \mathop = 1}^{N_f} p_{2 \paren {j + 1} }^{\map f {-j} }$

We show that $\phi : \SS \to \N$ is an injection.

Suppose that $f, g \in \SS$ and that $\map \phi f = \map \phi g$.

We have:

$\ds 2^{\map f 0} \prod_{j \mathop = 1}^{N_f} p_{2 j + 1}^{\map f j} \prod_{j \mathop = 1}^{N_f} p_{2 \paren {j + 1} }^{\map f {-j} } = 2^{\map g 0} \prod_{j \mathop = 1}^{N_g} p_{2 j + 1}^{\map g j} \prod_{j \mathop = 1}^{N_g} p_{2 \paren {j + 1} }^{\map g {-j} }$

Since $N_f$ and $N_g$ were picked to be least, we must have $N_f = N_g$.

Further from the Fundamental Theorem of Arithmetic, we must have:

$\map f j = \map g j$ for all $j \in \Z$.

Hence $f = g$.

Hence $\phi$ is an injection.

So $\SS$ is countable.

$\blacksquare$