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

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

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 (a) = f (b)$ 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 $|A |\leq| B|$ .

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{(m + n - 1) (m + 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, $(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,

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

is an integer, which means that $f (m, n) = \frac{(m + 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{aligned} 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{aligned}$

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

$(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 \dots \dots \dots \dots$

Step 4:

F one-to-one

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

$f (a, b) = f (m, n)$

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.

$(a, b) = (m, n)$

Then note that $f (a, b) = f (m, n)$ implies role="math" localid="1668423647696" $(a, b) = (m, n) f o r a l l (a, b) \in Z^{+} \times Z^{+}$ and for all $(m, n) \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^{t h}$ ordered pair in the path.

By definition of f:

$f (a, b) = c$

Then note that for every $c \in Z^{+}$ , there exists an element $(a, b) \in Z^{+} \times Z^{+}$ such that $f (a, b) = 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.

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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.

Step by Step Solution

Step 1:

Step 2:

Step 3:

Step 4:

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

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.

Step by Step Solution

Step 1:

Step 2:

Step 3:

Step 4:

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths

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.