The Set of Integers is Countably Infinite

Lemma 1: The set of integers, $\mathbb{Z}$ is countably infinite.

• Proof: Define a function $f : \mathbb{N} \to \mathbb{Z}$ by:

(1)

\begin{align} f(n) = \left\{\begin{matrix} \frac{n-1}{2} & \mathrm{if} \: n \: \mathrm{is \: odd} \\ -\frac{n}{2} & \mathrm{if} \: n \: \mathrm{is \: even} \end{matrix}\right. \end{align}

• The first few values of $f(n)$ are $f(1) = 0$, $f(2) = 1$, $f(3) = 1$, $f(4) = -2$, $f(5) = 2$, etc…

• We first show that $f$ is injective. Let $m, n \in \mathbb{N}$ and suppose that $f(m) = f(n)$. There are three cases to consider.

• Case 1: If $m$ and $n$ are both odd then $\frac{m-1}{2} = \frac{n-1}{2}$ which implies that $m = n$.

• Case 2: If $m$ and $n$ are both even then $-\frac{m}{2} = -\frac{n}{2}$ which implies that $m = n$.

• Case 3: If one of $m$ or $n$ is odd and the other is even, say without loss of generality that $m$ is odd and $n$ is even then $\frac{m - 1}{2} = -\frac{n}{2}$ and so $m - 1 = -n$. So $m + n = 1$ which is a contradiction since $m$ and $n$ are both at least equal to $1$.

• From all of the cases above we see that we must have that $m = n$ and so $f$ is injective.

• Clearly the function $f$ is surjective and this can be easily (but tediously shown) from the definition of $f$ above.

• Therefore $f$ is bijective and so $f$ is countably infinite. $\blacksquare$