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.

Leave a Reply

Your email address will not be published. Required fields are marked *