Question

Show that the set $Z^{+}\times Z^{+}$is countable.

Short answer

$Z^{+}\times Z^{+}$ is countable.

Step-by-step solution

Step 1:

DEFINITIONS:

A set is countable if it is finite or countably infinite.

A set is finite if it contains a limited number of elements.

A set is countably infinite if the set contains an unlimited number of elements and if there is a one-to-one correspondence with the positive integers.

The function f is one-to-one if and only if f (a) = f (b) implies that a = b for all a and b in the domain.

X is a subset of Y if every element of X is also and element of Y. Notation: $X\subseteq Y$

Definition (2): There is a one-to-one function from A to B if and only if $\left|A\right|\le \left|B\right|$.

Difference A - B : All elements in A that are NOT in B.

Step 2:

To proof: $Z^{+}\times Z^{+}$is countable.

PROOF:

Let us definite the function f as:

$f:Z^{+}\times Z^{+},f(\mathrm{m},\mathrm{n})=2^m\cdot 3^n$

Check that f is one-to-one: If f (a,b) = f (m,n) , then

$2^a\cdot 3^b=2^m\cdot 3^n$

Since are primes:

$\begin{array}{r}{2}^a=2^m\\ 3^b=3^n\end{array}$

Since the bases are the same, the powers also have to be the same.

a = m

b = n

By the definition of one-to-one, we have then shown that f is a one-to-one function.

By definition (2):

$\left|Z^{+}\times Z^{+}\right|\le \left|Z^{+}\right|$

A set A is countable if and only if $\left|A\right|\le \left|Z^{+}\right|$. Thus we have then shown that $Z^{+}\times Z^{+}$is countable.