Chapter 5.2, Problem 3E

a.

To determine

Prove that the given sets are denumerable.

Explanation of Solution

Given information:

  $D^{+}$ , the odd positive integers.

Calculation:

An infinite set is denumerable if it is equivalent to the set of natural number. We have given

  $D^{+}$ , the odd positive integers.

Now define the function $ffromNto{D}^{+},f\left(n\right)=2n-1$ .

  $\begin{array}{l}•fisonetoone\\ letmandnbenaturalnumberssuchthatf\left(m\right)=f\left(n\right)\\ f\left(m\right)=f\left(n\right)\\ \Rightarrow 2m-1=2n-1\\ \Rightarrow m=n\end{array}$

  $\begin{array}{l}•fisonto{D}^{+}\\ lety\in D^{+}begiventhenforn=\frac{y+1}{2}\\ f\left(n\right)=y\\ fisbijectivefunction.D^{+}\text{is denumerable}\end{array}$

Hence, proved.

b.

To determine

Prove that the given sets are denumerable.

Explanation of Solution

Given information:

  $3N$ , the positive integer multiples of $3$ .

Calculation:

An infinite set is denumerable if it is equivalent to the set of natural number. We have given

  $3N$ , the positive integer multiples of $3$ .

Now define the function $ffromNto{D}^{+},f\left(n\right)=2n-1$ .

  $\begin{array}{l}•fisonetoone.\\ letmandnbenaturalnumberssuchthatf\left(m\right)=f\left(n\right)\\ f\left(m\right)=f\left(n\right)\\ \Rightarrow 3m=3n\\ \Rightarrow m=n\end{array}$

  $\begin{array}{l}•fisonto3N\\ lety\in 3Nbegiventhenforn=\frac{y}{3}\\ f\left(n\right)=y\\ fisbijectivefunction.D^{+}\text{is denumerable}\text{.}\end{array}$

Hence, proved.

c.

To determine

Prove that the given sets are denumerable.

Explanation of Solution

Given information:

  $3Z$ , the integer multiples of $3$ .

Calculation:

An infinite set is denumerable if it is equivalent to the set of natural number. We have given

  $3Z$ , the integer multiples of $3$ .

Now define the function $ffromNto3Z,f\left(n\right)=\{\begin{array}{l}3n/2niseven\\ 3\left(1-n\right)/2,nisodd\end{array}$ .

  $\begin{array}{l}•fisonetoone.\\ letmandnbenaturalnumberssuchthatf\left(m\right)=f\left(n\right)\\ f\left(m\right)=f\left(n\right)\\ \Rightarrow 3n/2=3\left(1-n\right)/2\\ \Rightarrow 2n=1\end{array}$

  $\begin{array}{l}•fisonto3Z\\ lety\in 3Zbegiventhenforn=\{\begin{array}{l}\frac{2y}{3},y\ge 0\\ 1-\frac{2y}{3},y<0\end{array}\\ f\left(n\right)=y\\ fisbijectivefunction.3Z\text{is denumerable}\text{.}\end{array}$

Hence, proved.

d.

To determine

Prove that the given sets are denumerable.

Explanation of Solution

Given information:

  $\left\{n:n\in Nandn>6\right\}$

Calculation:

An infinite set is denumerable if it is equivalent to the set of natural number. We have given

  $\left\{n:n\in Nandn>6\right\}$

Now define the function $ffromNto\left\{n:n\in Nandn>6\right\}f\left(n\right)=n+6$ .

  $\begin{array}{l}•fisonetoone.\\ letmandnbenaturalnumberssuchthatf\left(m\right)=f\left(n\right)\\ f\left(m\right)=f\left(n\right)\\ \Rightarrow m+6=n+6\\ \Rightarrow m=n\end{array}$

  $\begin{array}{l}•fisonto\left\{n:n\in Nandn>6\right\}\\ lety\in \left\{n:n\in Nandn>6\right\}begiventhenforn=y-6\\ f\left(n\right)=y\\ fisbijectivefunction.\left\{n:n\in Nandn>6\right\}\text{is denumerable}\end{array}$

Hence, proved.

e.

To determine

Prove that the given sets are denumerable.

Explanation of Solution

Given information:

  $\left\{x:x\in Zandx<-12\right\}$

Calculation:

An infinite set is denumerable if it is equivalent to the set of natural number. We have given

  $\left\{x:x\in Zandx<-12\right\}$

Now define the function $ffromNto\left\{x:x\in Zandx<-12\right\},f\left(n\right)=-n-12$ .

  $\begin{array}{l}•fisonetoone.\\ letmandnbenaturalnumberssuchthatf\left(m\right)=f\left(n\right)\\ f\left(m\right)=f\left(n\right)\\ \Rightarrow -m-12=-n-12\\ \Rightarrow m=n\end{array}$

  $\begin{array}{l}•fisonto\left\{x:x\in Zandx<-12\right\}\\ lety\in \left\{x:x\in Zandx<-12\right\}begiventhenforn=-y-12\\ f\left(n\right)=y\\ fisbijectivefunction.\left\{x:x\in Zandx<-12\right\}\text{is denumerable}\end{array}$

Hence, proved.

f.

To determine

Prove that the given sets are denumerable.

Explanation of Solution

Given information:

  $N-\left\{5,6\right\}$

Calculation:

An infinite set is denumerable if it is equivalent to the set of natural number. We have given

  $N-\left\{5,6\right\}$

Now define the function $ffromNtoN-\left\{5,6\right\},f\left(n\right)=\{\begin{array}{l}n,n<5\\ n+2,n\ge 5\end{array}$ .

  $\begin{array}{l}•fisonetoone.\\ letmandnbenaturalnumberssuchthatf\left(m\right)=f\left(n\right)\\ f\left(m\right)=f\left(n\right)\\ assumem=n+2\\ thisiscontradiction\\ \Rightarrow m=n\end{array}$

  $\begin{array}{l}•fisontoN-\left\{5,6\right\}\\ lety\in N-\left\{5,6\right\}begiventhenforn=\{\begin{array}{l}y,y<5\\ y-2,\ge 5\end{array}\\ f\left(n\right)=y\\ fisbijectivefunction.N-\left\{5,6\right\}\text{is denumerable}\text{.}\end{array}$

Hence, proved.

g.

To determine

Prove that the given sets are denumerable.

Explanation of Solution

Given information:

  $\left\{\left(x,y\right)\in N\times R:xy=1\right\}$

Calculation:

An infinite set is denumerable if it is equivalent to the set of natural number. We have given

  $\left\{\left(x,y\right)\in N\times R:xy=1\right\}$

Now define the function $ffromNto\left\{\left(x,y\right)\in N\times R:xy=1\right\},f\left(x\right)=\left(x,\frac{1}{x}\right)$ .

  $\begin{array}{l}•fisonetoone.\\ letmandnbenaturalnumberssuchthatf\left(x\right)=f\left(y\right)\\ f\left(x\right)=f\left(y\right)\\ \Rightarrow \left(x,\frac{1}{x}\right)=\left(y,\frac{1}{y}\right)\\ \Rightarrow x=y\end{array}$

  $\begin{array}{l}•fisonto\left\{\left(x,y\right)\in N\times R:xy=1\right\}\\ lety\in \left\{\left(x,y\right)\in N\times R:xy=1\right\}begiventhenforn=x,y\\ f\left(n\right)=x,y\\ fisbijectivefunction.\left\{\left(x,y\right)\in N\times R:xy=1\right\}\text{is denumerable}\text{.}\end{array}$

Hence, proved.

h.

To determine

Prove that the given sets are denumerable.

Explanation of Solution

Given information:

  $\left\{x\in Z:x=1\left(\mathrm{mod}5\right)\right\}$

Calculation:

An infinite set is denumerable if it is equivalent to the set of natural number. We have given

  $\left\{x\in Z:x=1\left(\mathrm{mod}5\right)\right\}$

Now define the function $ffromNto\left\{x\in Z:x=1\left(\mathrm{mod}5\right)\right\},f\left(k\right)=\left(5k+1\right)$ .

  $\begin{array}{l}•fisonetoone.\\ letxandybenaturalnumberssuchthatf\left(x\right)=f\left(y\right)\\ f\left(x\right)=f\left(y\right)\\ \Rightarrow \left(x,\frac{1}{x}\right)=\left(y,\frac{1}{y}\right)\\ \Rightarrow x=y\end{array}$

  $\begin{array}{l}•fisonto\left\{x\in Z:x=1\left(\mathrm{mod}5\right)\right\}\\ lety\in \left\{x\in Z:x=1\left(\mathrm{mod}5\right)\right\}begiventhenforn=x,y\\ f\left(n\right)=x,y\\ fisbijectivefunction.\left\{x\in Z:x=1\left(\mathrm{mod}5\right)\right\}\text{is denumerable}\end{array}$

Hence, proved.