StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q31E

Expert-verifiedFound in: Page 177

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**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.**

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

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|$ .

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}^{+}$ .

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.

$(1,1)(2,1)(3,1)(4,1)\dots \phantom{\rule{0ex}{0ex}}(1,2)(2,2)(3,2)(4,2)\dots \phantom{\rule{0ex}{0ex}}(1,3)(2,3)(3,3)(4,3)\dots \phantom{\rule{0ex}{0ex}}(1,4)(2,4)(3,4)(4,4)\dots \phantom{\rule{0ex}{0ex}}(1,5)(2,5)(3,5)(4,5)\dots \phantom{\rule{0ex}{0ex}}\cdots \cdots \cdots \cdots $

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.

94% of StudySmarter users get better grades.

Sign up for free