Question

Prove that the set of integers is countable.

Answer 1

An infinite set is countable if and only if it is possible to list the elements of the set in a sequence.

To list the integers in a sequence 0,-1,1,-2,2….

A function f from the set of natural numbers to the set of integers defined by

$f(n)=\left\{\begin{matrix} (n-1)/2, \; n \;is\;odd & \\ n/2, \; n \;is \; even& \end{matrix}\right.$

To show that this function is countable.

That is to prove that the function is a bijection.

(1) To prove that f is injective:

Let m and n be two even numbers, then

$f(m) = \frac{m}{2} \\ f(n) = \frac{n}{2} \\ f(m) = f(n) \\ \frac{m}{2} = \frac{n}{2} \\ m=n$

Therefore f is injective.

(2) To prove that f is surjective:

Let t be negative then t appears even position in the sequence

$f(2k)= -\frac{2k}{2}=t$

with t= -k

This implies that for every negative value of t in Z there is a natural number 2k.

Let t be positive then t appears odd position in the sequence

$f(2k-1) = \frac{2k-1-1}{2}=\frac{2k-2}{2}=t$

with t=k

This implies that for every positive value t in Z there is a natural number 2k-1.

Therefore f is surjective.

Then f is both injective and surjective implies that f is bijection.

There the set of integers is countable.