Show that the set of all integer numbers is countableSolutio

Show that the set of all integer numbers is countable.

Solution

We can list the integers in a sequence:       0, 1, 1, 2, 2, 3, 3 ,………..0 Let f be a function from N  to Z defined as When n is even:    f(n) = n/2 When n is odd:     f(n) = (n1)/2 that generates this list.  We now show that this function   is a bijection. First we show that it is injective by case analysis on the parity of N.

Let m and n be two even natural numbers, then   f(m) = m/2 and f(n) = n/2, it follows that f(m)=f(n) implies m=n. Let m and n be two odd natural numbers, then f(m) = (m1)/2 and f(n) = (n1)/2, it follows that f(m)=f(n) implies m=n. Therefore, f is injective. We now show that f is surjective by case analysis on the sign of some integer t in Z. Let t be positive, then t will appear in an even position in the sequence, thus f(2k)=2k/2=t with t=k. This implies that for every positive value t in  Z there is a natural number 2k. Let t be negative, then t will appear in an odd position in the sequence, thus f(2k1)=(2k11)/2=t with t=k.  This implies that for every negative value t in Z there is a natural number 2k1. Therefore, f is surjective. (QED)