# Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.25

25. Show that the set of all integers greater than -100 is countable.

Solution: In order to prove that the set of all integers greater than -100 is countable, it suffices to prove that the set of integers $\mathbb{Z}$ is countable. This follows from the fact that the subset of a countable set is countable.

We can the list the integers in a sequence
0,1,-1,2,-2,3,-3,…
We define a function
$f:\mathbb{N} \rightarrow \mathbb{Z}$

This is defined as
$f(n)=\left\{\begin{matrix} \frac{n}{2}&\text{n is even} \\ \frac{-(n-1)}{2}& \text{n is odd}\end{matrix}\right.$

We now show that $f$ is a bijection.
First we show that it is injective by case analysis on the parity of $\mathbb{N}$
Case 1
If $m,n$ are two even natural numbers
Then
$f(m)=\frac{m}{2}$
$f(n)=\frac{n}{2}$
It follows that
$f(m)=f(n)$
Implies that
$m=n$
Case 2
If $m,n$ are two odd natural numbers
Then
$f(m)=-\frac{m-1}{2}$
$f(n)=-\frac{n-1}{2}$
It follows that
$f(m)=f(n)$
Implies that
$m=n$
Therefore $f$ is injective.
We now show that $f$ is surjective by case analysis on the sign of some integer $t$ in $\mathbb{Z}$
Case 1
If $t$ is positive, then $t$ will appear in an even position in the sequence.
Thus,
$f(2k)=\frac{2k}{2}$
$=t$
With
$t=k$
This implies that for every positive value $t$ in $\mathbb{Z}$ there is a natural number $2k$
Case 2
If $t$ is negative, then $t$ will appear in an odd position in the sequence.
Thus,
$f(2k-1)=-\frac{(2k-1)-1}{2}$
$=t$
With
$t=-k$
This implies that for every negative value $t$ in $\mathbb{Z}$ there is a natural number $2k-1$
Therefore, $f$ is surjective
Hence, $\mathbb{Z}$ is countable set.
Now we define the sequence
$a_n=n-100$
$>-100$
For $n \in \mathbb{N}$
This is clearly a subset of $\mathbb{Z}$ and so is countable.