Chapter 5.1, Problem 2E

a.

To determine

Find the cardinality $k$ of finite sets and one-to-one correspondence from the set to $N_k$ .

Answer to Problem 2E

  $10$

Explanation of Solution

Given information:

  $\left\{1,2,4,8,16,32,64,128,256,512\right\}$

Calculation:

Here we will consider the following set:

  $\left\{1,2,4,8,16,32,64,128,256,512\right\}$

Now, suppose $A=\left\{1,2,4,8,16,32,64,128,256,512\right\}$

As the number of elements in set $A$ is $10$ .

Thus, cardinality of $A$ is $10$ .

Now, define a function $f:A\to byf\left(1\right)=10$ and $f\left(2^n\right)=n$ for $n=1,2,3,\mathrm{...9}$

Now, we prove that $f$ is one-one:

  $\begin{array}{l}f\left(2^m\right)=f\left(2^n\right)\\ m=n\\ 2^m=2^n\end{array}$

Thus, $f$ is one-one.

Now, to prove that $f$ is onto we have to prove that if for every element $n$ in the co-domain of $f$ there should at least one element in the domain $A$ such that $f\left(2^n\right)=n$ .

Let $x\in {\mathbb{N}}_9$ (co-domain)

Let $y=2^x$ in $A$ (domain)

  $f\left(y\right)=f\left(2^x\right)$

Thus, for $x\in {\mathbb{N}}_9$ (co-domain) there exists $y=2^x$ in $A$ (domain)such that $f\left(y\right)=x$ .

Thus, $f$ is onto.

Hence, there is one-to-one correspondence from set $A$ to set ${\mathbb{N}}_9$ .

b.

To determine

Find the cardinality $k$ of finite sets and one-to-one correspondence from the set to ${\mathbb{N}}_k$ .

Answer to Problem 2E

  $4$

Explanation of Solution

Given information:

  $\left\{x\in ℂ:x^4=1\right\}$

Calculation:

Here we will consider the following set:

  $\left\{x\in ℂ:x^4=1\right\}$

Now, suppose $A=\left\{x\in ℂ:x^4=1\right\}$

As, $1^4=1,{\left(-1\right)}^4=1,i^4=1$ and ${\left(-i\right)}^4=1$

Thus, $1\in A,-1\in A,i\in A$ and $-i\in A$

  $A=\left\{x\in ℂ:x^4=1\right\}=\left\{1,-1,i,-i\right\}$

As the number of elements in set $A$ is $4$ .

Thus, cardinality of $A$ is $4$ .

Now, define a function $f:A\to {{\displaystyle }}_{4}byf\left(i^n\right)=n$

Now, we prove that $f$ is one-one:

  $\begin{array}{l}f\left(i^m\right)=f\left(i^n\right)\\ m=n\\ i^m=i^n\end{array}$

Thus, $f$ is one-one.

Now, to prove that $f$ is onto we have to prove that if for every element $n$ in the co-domain of $f$ there should at least one element in the domain $A$ such that $f\left(i^n\right)=n$ .

Let $x\in {ℂ}_4$ (co-domain)

Let $y=i^x$ in $A$ (domain)

  $f\left(y\right)=f\left(i^x\right)$

Thus, for $x\in {ℂ}_4$ (co-domain) there exists $y=i^x$ in $A$ (domain)such that $f\left(y\right)=x$ .

Thus, $f$ is onto.

Hence, there is one-to-one correspondence from set $A$ to set ${ℂ}_4$ .

c.

To determine

Find the cardinality $k$ of finite sets and one-to-one correspondence from the set to ${\mathbb{N}}_k$ .

Answer to Problem 2E

  $7$

Explanation of Solution

Given information:

  $\left\{x\in \mathbb{Z}:x^2<11\right\}$

Calculation:

Here we will consider the following set:

  $\left\{x\in \mathbb{Z}:x^2<11\right\}$

Now, suppose $A=\left\{x\in \mathbb{Z}:x^2<11\right\}$

As, ${\left(-3\right)}^2=9<11,{\left(-2\right)}^2=4<11,{\left(-1\right)}^2=1<11,0^2=0<11$ and $1^2=1<11,2^2=4<11,3^2=9<11$ .

Thus, $-3\in A,-2\in A,-1\in A,0\in A,1\in A,2\in A$ and $3\in A$

  $A=\left\{x\in \mathbb{Z}:x^2<11\right\}=\left\{-3,-2,-1,0,1,2,3\right\}$

As the number of elements in set $A$ is $7$ .

Thus, cardinality of $A$ is $7$ .

Now, define a function $f:A\to {{\displaystyle }}_{7}byf\left(n\right)=n+4$

Now, we prove that $f$ is one-one:

  $\begin{array}{l}f\left(m\right)=f\left(n\right)\\ m+4=n+4\\ m=n\end{array}$

Thus, $f$ is one-one.

Now, to prove that $f$ is onto we have to prove that if for every element $n$ in the co-domain of $f$ there should at least one element in the domain $A$ such that $f\left(n\right)=n+4$ .

Let $x\in {\mathbb{Z}}_7$ (co-domain)

Let $y=x-4$ in $A$ (domain)

  $\begin{array}{l}f\left(y\right)=f\left(x-4\right)\\ x-4+4\\ x\end{array}$

Thus, for $x\in {\mathbb{Z}}_7$ (co-domain) there exists $y=x-4$ in $A$ (domain)such that $f\left(y\right)=x$ .

Thus, $f$ is onto.

Hence, there is one-to-one correspondence from set $A$ to set ${\mathbb{Z}}_7$ .

d.

To determine

Find the cardinality $k$ of finite sets and one-to-one correspondence from the set to ${\mathbb{N}}_k$ .

Answer to Problem 2E

  $10$

Explanation of Solution

Given information:

  $\left\{\left(x,y\right)\in \mathbb{N}\times \mathbb{N}:x+y<6\right\}$

Calculation:

Here we will consider the following set:

  $\left\{\left(x,y\right)\in \mathbb{N}\times \mathbb{N}:x+y<6\right\}$

Now, suppose $A=\left\{\left(x,y\right)\in \mathbb{N}\times \mathbb{N}:x+y<6\right\}$

As, $1+1<6,1+2<6,1+3<6,1+4<6,2+1<6,2+2<6,2+3<6,3+1<6,3+2<6$ and $4+1<6$ .

Thus,

  $\begin{array}{l}\left(1,1\right)\in A,\left(1,2\right)\in A,\left(1,3\right)\in A,\left(1,4\right)\in A,\left(2,1\right)\in A,\\ \left(2,2\right)\in A,\left(2,3\right)\in A,\left(3,1\right)\in A,\left(3,2\right)\in A,\left(4,1\right)\in A\end{array}$

As the number of elements in set $A$ is $10$ .

Thus, cardinality of $A$ is $10$ .

Now, pairing of $A$ and ${\mathbb{N}}_{10}$ is:

  $\begin{array}{lll}A\hfill & f:\hfill & {\mathbb{N}}_{10}\hfill \\ \left(1,1\right)\hfill & \to \hfill & 1\hfill \\ \left(2,1\right)\hfill & \to \hfill & 2\hfill \\ \left(1,2\right)\hfill & \to \hfill & 3\hfill \\ \left(3,1\right)\hfill & \to \hfill & 4\hfill \\ \left(2,2\right)\hfill & \to \hfill & 5\hfill \\ \left(1,3\right)\hfill & \to \hfill & 6\hfill \\ \left(4,1\right)\hfill & \to \hfill & 7\hfill \\ \left(3,2\right)\hfill & \to \hfill & 8\hfill \\ \left(2,3\right)\hfill & \to \hfill & 9\hfill \\ \left(1,4\right)\hfill & \to \hfill & 10\hfill \end{array}$

Hence, this pattern defines one-to-one correspondence from set $A$ to ${\mathbb{N}}_{10}$ .