The Set of Integers is Countably Infinite

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