• :00Days
  • :00Hours
  • :00Mins
  • 00Seconds
A new era for learning is coming soonSign up for free
Log In Start studying!

Select your language

Suggested languages for you:
Answers without the blur. Sign up and see all textbooks for free! Illustration


Discrete Mathematics and its Applications
Found in: Page 177
Discrete Mathematics and its Applications

Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.


Short Answer

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

Z+×Z+ is countable.

See the step by step solution

Step by Step Solution

Step 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 fa=fb implies that a=b for all a and b in the domain.


There is one-to-one function A to B if only if AB .

Step 2:


To proof: Z+×Z+ is countable.


Let definite the function f as:


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


is an integer, which means that f(m,n)=(m+n-1)(m+1-2)2+mZ+ .

Step 3:

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


Then note that fm,n represents the position of (m,n) in the path created by the diagram below, with (1,1) the 1th position, (1,2) the 2thposition, (2,1) the 3th position, etc.


Step 4:

F one-to-one

Let assume that a,bZ+×Z+ and m,nZ+×Z+ such that a and b have the same image.


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.


Then note that fa,b=fm,n implies role="math" localid="1668423647696" a,b=m,n for all a,bZ+×Z+ and for all m,nZ+×Z+ . By the definition of one-to-one, f is then one-to-one.

F onto

Let role="math" localid="1668423698801" cZ+ .

Let (a,b) be the cth ordered pair in the path.

By definition of f:


Then note that for every cZ+ , there exists an element a,bZ+×Z+ such that fa,b=c . By the definition of onto, f is then onto.


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+×Z+ . This then also means that Z+×Z+ is countable as Z+ is countable.

Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.

Sign up for free
94% of StudySmarter users get better grades.