Question

Show that $Z^{+}\times Z$is countable by showing that the polynomial function $f:Z^{+}\to Z^{+}\to Z^{+}$with $f(m,n)=(m+n-2)(m+n-1)/2+m$ is one-to-one and onto.

Short answer

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

Step-by-step solution

Step 1:

DEFINITION (1)

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

A set is finite if it contains a limited number of elements (thus it is possible to list every single element in the set).

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\left(a\right)=f\left(b\right)$implies that $a=b$for all a and b in the domain.

DEFINITION (2)

There is one-to-one function A to B if only if $\left|A\left|\le \right|B\right|$.

Step 2:

SOLUTION

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

PROOF:

Let definite the function f as:

$f:Z^{+}\times Z^{+}\to Z^{+},f(m,n)=\frac{(\mathrm{m}+\mathrm{n}-1)(\mathrm{m}+\mathrm{n}-2)}{2}+m$

Note: Since an odd number is always follows by an even number and an even number is always followed by an odd number, $\left(m+n-1\right)$or $\left(m+n-2\right)$is even (but not both) and the other element is then odd. The even term is then divisible by and thus,

$\frac{(m+n-1)(m+n-2)}{2}$

is an integer, which means that $f(m,n)=\frac{(m+\mathrm{n}-1)(m+1-2)}{2}+m\in Z^{+}$.

Step 3:

Let us first evaluate the formula at a few pairs mentioned in the diagram.

$\begin{array}{r}f(1,1)=\frac{(1+1-1)(1+1-2)}{2}+1=\frac{0}{2}+1=1\\ f(1,2)=\frac{(1+2-1)(1+2-2)}{2}+1=\frac{2}{2}+1=2\\ f(2,1)=\frac{(2+1-1)(2+1-2)}{2}+2=\frac{2}{2}+2=3\\ f(1,3)=\frac{(1+3-1)(1+3-2)}{2}+1=\frac{6}{2}+1=4\\ f(2,2)=\frac{(2+2-1)(2+2-2)}{2}+2=\frac{6}{2}+2=5\\ f(3,1)=\frac{(3+1-1)(3+1-2)}{2}+3=\frac{6}{2}+3=6\end{array}$

Then note that $f\left(m,n\right)$represents the position of (m,n) in the path created by the diagram below, with (1,1) the $1^{th}$position, (1,2) the $2^{th}$position, (2,1) the $3^{th}$position, etc.

$$\begin{gathered} (1,1)(2,1)(3,1)(4,1)\dots \\ (1,2)(2,2)(3,2)(4,2)\dots \\ (1,3)(2,3)(3,3)(4,3)\dots \\ (1,4)(2,4)(3,4)(4,4)\dots \\ (1,5)(2,5)(3,5)(4,5)\dots \\ \cdots \cdots \cdots \cdots \end{gathered}$$

Step 4:

F one-to-one

Let assume that $\left(a,b\right)\in Z^{+}\times Z^{+}$and $\left(m,n\right)\in Z^{+}\times Z^{+}$such that a and b have the same image.

$f\left(a,b\right)=f\left(m,n\right)$

By definition of the function f, the image of f then represents the same element in the path created in the diagram. However, each value is unique along the path and thus the corresponding values need to be in the same location.

$\left(a,b\right)=\left(m,n\right)$

Then note that $f\left(a,b\right)=f\left(m,n\right)$implies role="math" localid="1668423647696" $\left(a,b\right)=\left(m,n\right)forall\left(a,b\right)\in Z^{+}\times Z^{+}$and for all $\left(m,n\right)\in Z^{+}\times Z^{+}$. By the definition of one-to-one, f is then one-to-one.

F onto

Let role="math" localid="1668423698801" $c\in Z^{+}$.

Let (a,b) be the $c^{th}$ordered pair in the path.

By definition of f:

$f\left(a,b\right)=c$

Then note that for every $c\in Z^{+}$, there exists an element $\left(a,b\right)\in Z^{+}\times Z^{+}$such that $f\left(a,b\right)=c$. By the definition of onto, f is then onto.

Countable

Showed that f is onto and one-to-one, which implies that f is a one-to-one correspondence between $Z^{+}$and role="math" localid="1668423836805" $Z^{+}\times Z^{+}$. This then also means that $Z^{+}\times Z^{+}$ is countable as $Z^{+}$is countable.