Show that the set D = N × Z is countable.

Question

We are told to find injection between the set D and the set of natural numbers N but I'm not really sure how to do that in this case

Answer 1

First, have you shown that Z is countable? This would entail an injection f from Z to N. An example would be z \mapsto abs(3z) + z/abs(z) + 2 if z is not 0 and 0 \mapsto 1, where abs is the absolute value. Or z \mapsto abs(2z) + (z % 2) + 1, where "%" is the modulus, i.e. remainder when divided by 2, i.e. x % 2 = 1 if x is odd and = 0 if x is even. It is a good exercise to show these are injections. Note \mapsto is the latex symbol of a right arrow with a vertical bar at the end of its tail. |->

 

Pick 2 primes. 2 and 3, for example. Define

 

g: (n,z) \mapsto 2ⁿ3^f(z). We claim this is an injection.

 

Suppose 2ⁿ3^f(z)=2^m3^f(u). Then by the fundamental theorem of arithmetic n=m and f(z)=f(u). Then by the injectivity of f, z = u. Therefore g is an injection. Therefore the maximum cardinality of D is \aleph_0 (the first infinite cardinal), i.e. countable. It remains to show that D is infinite. This can be done by finding an injection from N into D. That can be done by n \mapsto (n,0).

 

Another approach to the problem is to establish part of what is called cardinal arithmetic, namely that the cartesian product of two infinite cardinals a and b has cardinality max{a,b}. In other words, it is a general fact that the cartesian product of a countable cardinal and a finite or countable cardinal is countable.

 

I hope that helps!