Question

Show that the set Z^+ × Z^+ is countable.
Z^+ × Z^+ denotes the Cartesian Product of the set of positive integers and the set of positive integers.

Answer 1

A set is said to be countable if it is finite in nature or let's say countably infinite.

To proof : Z^+ × Z^ is countable.

One easy way is to demonstrate that it is an injective function .

f: Z^+ × Z^→Z

Since we know Z is countable. If there is an injection from A to B, then |A|≤|B|

Here’s an example to show that N×N is countable; extending this to Z^+ × Z^ should be easy.

Look at the function f(m,n) = 2^m.3^n

Check that f is one-to-one:

if f(m,n) = f(j,k)

then:

2^j.3^k = 2^m.3^n

Since 2 and 3 are prime numbers:

2^j = 2^m

3^k = 3^n

Clearly, by the Fundamental Theorem of Arithmetic, if f(m,n) = f(j,k) then

m = j

n = k

So, the function is an injection.

By defination : |Z^+ × Z^| <= |Z^+|

A set S is countable if and only if |S| <= |Z^+|

Thus, Z^+ × Z^ is countable.