# How to Prove It - Solutions

## Chapter - 6, Mathematical Induction

### Summary

• Suppose $R$ is a relation on set $A$. $R^n = R \circ R \circ \cdot \cdot \cdot \circ R$(n times).
• Suppose $R$ is a relation on set $A$. Then $R^m \circ R^n = R^{m+n}$.
• Transitive closure of relation $R$ on set $A$ is $\cup_{n \in \mathbb Z^+} R^n$.

Soln1

(a)

We need to prove the following:

• $\cap \mathcal F \ne \phi$.
• $\cap \mathcal F$ is closed under $f$. Or $\forall x \in \cap \mathcal F (f(x) \in \cap \mathcal F)$.
• $B \subseteq \cap \mathcal F \subseteq A$.
• $\cap \mathcal F$ is the closure of $B$ under $f$.

Now we will prove them one by one:

• Proof for: $\cap \mathcal F \ne \phi$.

Since $f: A \to A$, it follows that $\forall x \in A(f(x) \in A)$. Thus $A$ is closed under $f$. Also since $B \subseteq A$, it follows that $A \in \mathcal F$. Thus $\mathcal F \ne \phi$.

• Proof for: $\cap \mathcal F$ is closed under $f$.

Suppose $x \in \cap \mathcal F$. Suppose $C$ is an arbitrary set in $\mathcal F$. Since $\cap \mathcal F \subseteq C$, it follows that $x \in C$. Since $C$ is closed under $f$ and $x \in C$, it follows that $f(x) \in C$. Since $C$ was arbitrary element of $\mathcal F$, it follows that $\forall C \in \mathcal F(f(x) \in C)$. It follows that $f(x) \in \cap \mathcal F$. Since $x$ is arbitrary, it follows that $\forall x \in \cap \mathcal F (f(x) \in \cap \mathcal F)$.

• Proof for: $B \subseteq \cap \mathcal F \subseteq A$.

Suppose $x \in \cap \mathcal F$. Suppose $C$ is an arbitrary set in $\mathcal F$. Since $\cap \mathcal F \subseteq C$, it follows $x \in C$. Since $C \subseteq A$, it follows $x \in A$. Since $x$ is arbitrary, thus $\cap \mathcal F \subseteq A$.

Suppose $x \in B$. Suppose $C$ is an arbitrary set in $\mathcal F$. Since $B \subseteq C$, it follows $x \in C$. Since $C$ is an arbitrary set, it follows $\forall C \in \mathcal F(x \in C)$. It follows that $x \in \cap \mathcal F$. Since $x$ is arbitrary, it follows that $B \subseteq \cap \mathcal F$.

• Proof for: $\cap \mathcal F$ is the closure of $B$ under $f$.

Thus we need to prove that $\cap \mathcal F$ the smallest set closed under $f$ such that $B \subseteq \cap \mathcal F \cap A$.
Suppose $C$ is a set such that $B \subseteq C \subseteq A$ and $C$ is closed under $f$. Thus $C \in \mathcal F$. It follows that $\cap \mathcal F \subseteq C$. Since $\cap \mathcal F$ is closed under $f$ and $B \subseteq \cap \mathcal F \cap A$ and $\cap \mathcal F \subseteq C$, it follows that $\cap \mathcal F$ is the smallest set closed under $f$ such that $B \subseteq \cap \mathcal F \cap A$.

(b)

Suppose $C = \cup_{n \in \mathbb Z^+} B_n$

We need to prove the following:

• $B \subseteq C \subseteq A$.
• $C$ is closed under $f$.
• $C$ is the smallest set closed under $f$ such that $B \subseteq C \subseteq A$.

Now we shall prove each as follows:

• $B \subseteq C \subseteq A$:

It directly follows that $B = B_1 \subseteq \cup_{n \in \mathbb Z^+} B_n$. Also since $f: A \to A$ and $B_{n+1} = \{ f(x) \, \vert \, x \in B_n \}$, if follows that $B_n \subseteq A$. Thus $\cup_{n \in \mathbb Z^+} B_n \subseteq A$.

• $C$ is closed under $f$:

Suppose $x \in C$. Thus for some $n \in Z^+$, $x \in B_n$. It follows that $f(x) \in B_{n+1}$. But $B_{n+1} \subseteq C$. Thus $f(x) \in C$. Since $x$ was arbitrary, it follows that $\forall x \in C(f(x) \in C)$. Thus $C$ is closed under $f$.

• $C$ is the smallest set closed under $f$ such that $B \subseteq C \subseteq A$:

Suppose there is a set $D$ closed under $f$ such that $B \subseteq D \subseteq A$. Thus we need to prove that $C \subseteq D$. Thus we need to prove that $\forall n \in Z^+ (B_n \subseteq D)$. We shall prove this using induction:

Base Case:

For $n = 1, B_1 = B$. Thus by assumption for our set $D$, $B \subseteq D$.

Induction Step:

Suppose for $n \in Z^+$, $B_n \subseteq D$.

Suppose $y \in B_{n+1}$. Thus by the definition of $B_n$, it follows that there exists some $x \in B_n$ such that $y = f(x)$. But by our hypothesis, $B_n \subseteq D$, thus $x \in D$. Since $D$ is a closed set and $x \in D$, it follows that $f(x) \in D$, or $y \in D$. Since $y$ is arbitrary, it follows that $B_{n+1} \in D$.

Thus $\forall n \in Z^+ (B_n \subseteq D)$, or $\cup_{n \in \mathbb Z^+} B_n \subseteq D$. Thus $C \subseteq D$.

Soln2

Closure of set $\{ 0 \}$ under $f$ is : $\{ 0,1,2,3,\,.... \}$.

Soln3

This can be proved in a similar way like in Ex-1 part(a).

Suppose $\mathcal H = \{ C \, \vert \, B \subseteq C \subseteq A \text{ and } \forall f \in \mathcal F(C \text{ is closed under } f) \}$.

We shall now prove that $\cap \mathcal H \ne \phi$ and $\cap \mathcal H$ is closure of $B$ on $f$. We will prove this by proving the following:

• $\cap \mathcal H \ne \phi$.
• $\forall f \in \mathcal F(\cap \mathcal H \text{ is closed on } f )$.
• $B \subseteq \cap \mathcal H \subseteq A$.
• $\cap \mathcal H$ is the smallest set such that $B \subseteq \cap \mathcal H \subseteq A$ and $\forall f \in \mathcal F(\cap \mathcal H \text{ is closed on } f )$.

Lets prove each of them:

• $\cap \mathcal H \ne \phi$.

We know that $B \subseteq A \subseteq A$. Also $\forall f \in \mathcal F(A \text{ is closed on } f )$. Thus $A \in \mathcal H$. It follows that $\cap \mathcal H \ne \phi$.

• $\forall f \in \mathcal F(\cap \mathcal H \text{ is closed on } f )$.

Suppose $f \in \mathcal F$. Suppose $x \in \cap \mathcal H$. Suppose $C$ is an arbitrary element of $\mathcal H$. Since $\cap \mathcal H \subseteq C$, it follows that $x \in C$. Since $\forall f \in \mathcal F(C \text{ is closed on } f )$, it follows that $f(x) \in C$. Since $C$ was arbitrary, it follows that $\forall C \in \mathcal H(f(x) \in C)$. Thus $f(x) \in \cap \mathcal H$. Since $x$ was arbitrary, it follows that $\cap \mathcal H$ is closed on $f$. Since $f$ is arbitrary, it follows that $\forall f \in \mathcal F(\cap \mathcal H \text{ is closed on } f )$.

• $B \subseteq \cap \mathcal H \subseteq A$.

Suppose $x \in \cap \mathcal H$. Suppose $C$ is an arbitrary element of $\mathcal H$. Since $\cap \mathcal H \subseteq C$, it follows that $x \in C$. Since $C \subseteq A$, it follows $x \in A$. Since $x$ is arbitrary, it follows that $\cap \mathcal H \subseteq A$.

Suppose $x \in B$. Suppose $C$ is an arbitrary element of $\mathcal H$. Since $C \subseteq B$, it follows that $x \in C$. Since $C$ was arbitrary, it follows that $\forall C \in \mathcal H(x \in C)$. Thus $x \in \cap \mathcal H$. Since $x$ is arbitrary, it follows $B \subseteq \cap \mathcal H$.

• $\cap \mathcal H$ is the smallest set such that $B \subseteq \cap \mathcal H \subseteq A$ and $\forall f \in \mathcal F(\cap \mathcal H \text{ is closed on } f )$.

Suppose $D$ is a set such that $B \subseteq D \subseteq A$ and $\forall f \in \mathcal F(D \text{ is closed on } f )$. Thus $D \in \mathcal H$. It follows that $\cap \mathcal H \subseteq D$. Thus $\cap \mathcal H$ is the smallest set such that $B \subseteq \cap \mathcal H \subseteq A$ and $\forall f \in \mathcal F(\cap \mathcal H \text{ is closed on } f )$.

Soln4

We shall follow the proof from Ex-1(b).

Suppose $B_1 = B$ and $\forall n > 1(B_{n+1} = \{ f(x,y) \, \vert \, \exists k < {n+1} (x \in B_k) \text{ and } \exists k < {n+1}(y \in B_k) \}$. Suppose $C = \cup_{n \in Z^+}B_n$.

Note that $B_{n+1}$ is different from $B_{n+1}$ in Ex-1 part(b).

Now we shall prove that $C$ is the closure of $B$ on $f$.

We need to prove the following:

• $B \subseteq C \subseteq A$.
• $C$ is closed under $f$.
• $C$ is the smallest set closed under $f$ such that $B \subseteq C \subseteq A$.

Now we shall prove each as follows:

• $B \subseteq C \subseteq A$:

It directly follows that $B = B_1 \subseteq \cup_{n \in \mathbb Z^+} B_n$. Also since $f: A \times A \to A$ and $B_{n+1} = \{ f(x,y) \, \vert \, x \in B_n \text{ and } y \in B_n \}$, if follows that $B_n \subseteq A$. Thus $\cup_{n \in \mathbb Z^+} B_n \subseteq A$.

• $C$ is closed under $f$:

Suppose $x \in C$. Suppose $y \in C$. Thus for some $m \in Z^+$, $x \in B_m$. Similarly for some $n \in Z^+$, $y \in B_n$. Now consider following cases:

• Case $m \ge n$

Then by definition of $B_m$, it follows that $f(x,y) \in B_{m+1}$. Thus $f(x,y) \in C$.

• Case $m < n$

Then by definition of $B_n$, it follows that $f(x,y) \in B_{n+1}$. Thus $f(x,y) \in C$.

Thus $f(x,y) \in C$ in all possible cases. Since $x$ and $y$ are arbitrary, it follows that $\forall x \in C \forall y \in C(f(x,y) \in C)$. Thus $C$ is closed on $f$.

• $C$ is the smallest set closed under $f$ such that $B \subseteq C \subseteq A$:

Suppose there is a set $D$ closed under $f$ such that $B \subseteq D \subseteq A$. Thus we need to prove that $C \subseteq D$. Thus we need to prove that $\forall n \in Z^+ (B_n \subseteq D)$. We shall prove this using strong induction:

Suppose $n$ is an arbitrary natural number. Suppose $\forall k < n(B_k \subseteq D)$(induction hypothesis). Consider the following cases:

• Case $n = 1$
For $n = 1, B_1 = B$. Thus by assumption for our set $D$, $B \subseteq D$.

• Case $n > 1$

Suppose $z \in B_n$. Since $n > 1$, it follows that $z = f(x,y)$ where $x \in B_k$ and $y \in B_l$ such that $k,l < n$. Since $k < n$ and $l < n$, then by our induction hypothesis $B_k \subseteq D$ and $B_l \subseteq D$. It follows that $x \in D$ as well as $y \in D$. Since $D$ is closed under $f$, it follows that $f(x,y) \in D$. Thus $z \in D$. Since $z$ was arbitrary, it follows that $B_n \subseteq D$.

Thus $\forall n \in Z^+ (B_n \subseteq D)$, or $\cup_{n \in \mathbb Z^+} B_n \subseteq D$. Thus $C \subseteq D$.

Soln5

Using Soln4, we have:
$B_1 = B = \{ x \, \vert \, x \text{ is prime number } \} = \{ 2,3,5,7,... \}$.
$B_2 = \{ 2 \times 2, 2 \times 3, 2 \times 5, 2 \times 7, .... , 3 \times 3, 3 \times 5, 3 \times 7, ..... \}$.

As we can see, $C = \cup_{n \in Z^+} B_n$ will consists of all possible products of prime numbers. Since every natural number greater than 1 can be expressed as a product of primes, it follows that $C$ contains all natural numbers other than one. Thus $C = \{ n \, \vert \, n \ge 2 \}$.

Soln6

(a)

Suppose $B_n$ is defined as follows:

For $n = 1$, $B_n = B_1 = B$.
For $n > 1$, $B_{n+1} = \{ f(x,y) \; \vert \; f \in \mathcal F \text{ and } \exists k < {n+1} (x \in B_k) \text{ and } \exists k < {n+1}(y \in B_k) \}$

Suppose $C = \cup_{i \in Z^+} B_n$. Now we will prove that $C$ is closure of $B$ under $\mathcal F$. We shall prove this by proving the following:

• $B \subseteq C \subseteq A$.
• $\forall f \in \mathcal F(C \text{ is closed under } f)$.
• $C$ is the smallest set closed under $\mathcal F$ such that $B \subseteq C \subseteq A$.

Lets prove each of the above:

• $B \subseteq C \subseteq A$.

Clearly $B_1 \subseteq \cup_{i \in Z^+} B_n$. Since $B_1 = B$, it follows that $B \subseteq C$.

Since $f: A \times A \to A$, We can clearly see that $B_n \subseteq A$. Since $C = \cup_{i \in Z^+} B_n$, it follows that $C \subseteq A$.

• $\forall f \in \mathcal F(C \text{ is closed under } f)$.

Or we may also say that we need to prove $\forall x \in C \forall y \in C (\forall f \in \mathcal F (f(x,y) \in C))$.

Suppose $x \in C$. Suppose $y \in C$. Since $C = \cup_{i \in Z^+} B_n$, it follows that for some $m \in \mathbb N$ and $n \in \mathbb N$ such that $x \in B_m$ and $y \in B_n$. Consider the following cases:

• Case $m \ge n$

Then by definition of $B_m$, it follows that $\forall f \in \mathcal F(f(x,y) \in B_{m+1})$. Since $B_{m+1} \subseteq C$, it follows that $\forall f \in \mathcal F(f(x,y) \in C)$.

• Case $m < n$

Then by definition of $B_n$, it follows that $\forall f \in \mathcal F(f(x,y) \in B_{n+1})$. Since $B_{n+1} \subseteq C$, it follows that $\forall f \in \mathcal F(f(x,y) \in C)$.

Thus from both cases $\forall f \in \mathcal F(f(x,y) \in C)$. Since $x$ and $y$ are arbitrary, it follows that $\forall x \in C \forall y \in C (\forall f \in \mathcal F (f(x,y) \in C))$.

• $C$ is the smallest set closed under $\mathcal F$ such that $B \subseteq C \subseteq A$.

Suppose there is a set $D$ closed under $f$ such that $B \subseteq D \subseteq A$. Thus we need to prove that $C \subseteq D$. Thus we need to prove that $\forall n \in Z^+ (B_n \subseteq D)$. We shall prove this using strong induction:

Suppose $n$ is an arbitrary natural number. Suppose $\forall k < n(B_k \subseteq D)$(induction hypothesis). Consider the following cases:

• Case $n = 1$
For $n = 1, B_1 = B$. Thus by assumption for our set $D$, $B \subseteq D$.

• Case $n > 1$

Suppose $z \in B_n$. Since $n > 1$, it follows that for some function $f \in \mathcal F$, $z = f(x,y)$ where $x \in B_k$ and $y \in B_l$ such that $k,l < n$. Since $k < n$ and $l < n$, then by our induction hypothesis $B_k \subseteq D$ and $B_l \subseteq D$, it follows that $x \in D$ as well as $y \in D$. Since $D$ is closed under $f$, it follows that $f(x,y) \in D$. Since $z$ is arbitrary, it follows that $B_n \subseteq D$.

Thus $\forall n \in Z^+ (B_n \subseteq D)$, or $\cup_{n \in \mathbb Z^+} B_n \subseteq D$. Thus $C \subseteq D$.

(b)

We know from part(a), that closure of $B$ on $\mathcal F$ is $C = \cup_{i \in Z^+} B_n$, where $B_n$ is defined as:

For $n = 1$, $B_n = B_1 = B$.
For $n > 1$, $B_{n+1} = \{ f(x,y) \; \vert \; f \in \mathcal F \text{ and } \exists k < {n+1} (x \in B_k) \text{ and } \exists k < {n+1}(y \in B_k) \}$

We are given that set $S = \{ a + b \sqrt 2 \; \vert \; a \in \mathbb Q, b \in \mathbb Q \}$. Also, it is given $B = \mathbb Q \cup \{ \sqrt 2 \}$.

We need to prove: $S = C$. Thus we shall prove:

• $S \subseteq C$.
• $C \subseteq S$.

Now we shall prove both statements:

• $S \subseteq C$.

Suppose $x \in S$. Thus for some $a \in \mathbb Q$ and $b \in \mathbb Q$, $x = a + b \sqrt 2$. Since $Q \subseteq B$, it follows that $\{ a,b \} \subseteq B$. Also since $\{ \sqrt 2 \} \subseteq B$, we can also say that $\{ a, b, \sqrt 2 \} \subseteq B$.
Since $\{ a, b, \sqrt 2 \} \subseteq B$, then by the definition of $B_n$ it follows that $g(b, \sqrt 2) \in B_2$. Thus $b \sqrt 2 \in B_2$. Similarly since $a \in B_1$ and $b \sqrt 2 \in B_2$, it follows that $f(a, b \sqrt 2) \in B_3$. Thus $a + b \sqrt 2 \in B_3$. Since $B_3 \subseteq C$, it follows that $a + b \sqrt 2 \in C$. Thus $x \in C$. Since $x$ was arbitrary, it follows that $S \subseteq C$.

• $C \subseteq S$.

Thus we need to prove that $\cup_{n \in Z^+} B_n \, \subseteq \, S$. We can prove this by proving that $\forall n \in Z^+ (B_n \subseteq S)$. We shall prove this using strong induction. Suppose $n$ is a natural number. Suppose our induction hypothesis is $\forall k < n(B_k \subseteq S)$.

We have following possible cases:

• Case $n = 1$.

Thus $B_n = B_1 = B$. Suppose $a \in \mathbb Q$. Thus $a = a + 0 \cdot \sqrt 2$. Thus $a \in S$. It follows that $Q \subseteq S$. Also $\sqrt 2 = 0 + 1 \cdot \sqrt 2 \in S$, it follows that $\sqrt 2 \in S$. Thus $Q \cup \{ \sqrt 2 \} \subseteq S$. Or $B \subseteq S$.

• Case $n > 1$.

Suppose $x \in B_n$. Since $n > 1$ and by the definition of $B_n$, there exist $p \in B_i$ and $q \in B_j$ such that either $x = f(p,q)$ or $x = g(p,q)$ where $i < n$ and $j < n$.
Since $i < n$ and $j < n$, then it follows from induction hypothesis that $B_i \subseteq S$ and $B_j \subseteq S$. Thus $p \in S$ and $q \in S$. Since $p \in S$, it follows that $p = a_1 + b_1 \sqrt 2$ where $a_1, b_1 \in \mathbb Q$. Similarly $q = a_2 + b_2 \sqrt 2$ where $a_2, b_2 \in \mathbb Q$.

Consider the following possible cases:

• $x = f(p,q)$
Thus $x = p + q = a_1 + b_1 \sqrt 2 + a_2 + b_2 \sqrt 2 = (a_1 + b_1) + (b_1 + b_2) \sqrt 2$. Thus $x \in S$.

• $x = g(p,q)$
Thus $x = pq = (a_1 + b_1 \sqrt 2)(a_2 + b_2 \sqrt 2)$
$= a_1a_2 + a_1 b_2 \sqrt2 + b_1 \sqrt 2 a_2 + b_1 \sqrt 2 b_2 \sqrt 2$
$= a_1a_2 + (a_1 b_2 + b_1 a_2) \sqrt 2 + 2 b_1 b_2$
$= (a_1a_2 + 2 b_1 b_2) + (a_1 b_2 + b_1 a_2) \sqrt 2$.
Thus $x \in S$.

Thus in both cases $x \in S$.

Since $x$ is arbitrary, it follows that $B_n \subseteq S$.

Thus in both cases $B_n \subseteq S$.

It follows that $C \subseteq S$.

Since $S \subseteq C$ and $C \subseteq S$, it follows that $S = C$.

(c)

Required set will be $S = \{ a + b 2^{(\frac 1 3)} + c 2^{(\frac 2 3)} \; \vert \; a \in \mathbb Q \text{ and } b \in \mathbb Q \text{ and } c \in \mathbb Q \}$.

Soln7

We will prove this by ordinary induction.

Base Case:

For $n = 1$, R^1 = R $and$ S^1 = S $. Since$ R \subseteq S $, it follows$ R^1 \subseteq S^1 $. Thus for$ n = 1 $,$ R^n \subseteq S^n $$. Induction step: Suppose theorem is correct for n. Thus for R^n \subseteq S^n. Now consider R^{n+1}. Suppose (a,c) \in R^{n+1}. Since R^{n+1} = R \circ R^n, it follows that there exists an element b such that (a,b) \in R and (b,c) \in R^n. By our hypothesis, R^n \subseteq S^n, it follows that (a,b) \in S and (b,c) S^n. Since S^{n+1} = S \circ S^n, it follows that (a,c) \in S^{n+1}. Since (a,c) is arbitrary, it follows that R^n \subseteq S^n. Soln8 (a) (R \cap S)^n \subseteq R^n \cap S^n. Since R \cap S \subseteq R and R \cap S \subseteq S, it follows from Ex-7, that (R \cap S)^n \subseteq R^n and (R \cap S)^n \subseteq S^n. Thus we can conclude that (R \cap S)^n \subseteq R^n \cap S^n. However R^n \cap S^n \nsubseteq (R \cap S)^n. Example: Suppose R = \{ (1,2), (2,3) \}, S = \{ (1,0), (0,3) \}. Thus R \cap S = \phi. Thus (R \cap S)^2 = \phi. But R^2 \cap S^2 = \{ (1,3) \} \cap \{(1,3)\} = \{ (1,3)\}. Thus R^n \cap S^n \nsubseteq (R \cap S)^n. (b) R^n \cup S^n \subseteq (R \cup S)^n. Since R \subseteq R \cup S and S \subseteq R \cup S, it follows from Ex-7, that R^n \subseteq (R \cup S)^n and S^n \subseteq (R \cup S)^n. Thus we can conclude that R^n \cup S^n \subseteq (R \cup S)^n. However (R \cup S)^n \nsubseteq R^n \cup S^n. Example: Suppose R = \{(1,2)\}, S = \{(2,3)\}. Thus R \cup S = \{ (1,2), (2,3) \}. Thus (R \cup S)^2 = \{(1,3)\}. But R^2 \cup S^2 = \phi \cup \phi = \phi. Thus (R \cup S)^n \nsubseteq R^n \cup S^n. Soln9 (a) Suppose m = d(a,b), and n = d(b.c) and suppose o = d(a,c). Thus (a,b) \in R^m and (b,c) \in R^n. Thus (a,c) \in R^n \circ R^m. Thus (a,c) \in R^{m+n}. Since o = d(a,c). it follows that (a,c) \in R^o. Suppose o > m+n. Since (a,c) \in R^{m+n} and o = d(a,c) is the smallest positive integer o such that (a, c) \in R_o, it follows that o \le m+n. But this contradicts with our assumption that o > m+n. Thus o \le m+n. (b) We are given that (a,c) \in S. Also we can directly see m \ge 1. Thus we need to prove: We need to prove: \forall m\in \mathbb N(m < d(a,c) \to \exists b \in A(d(a,b) = m \text{ and } d(b,c) = d(a,c) - m)). We will prove this using ordinary induction. • Base Case m = 1 Suppose m < d(a,c). Suppose n = d(a,c), thus (a,c) \in R^n. Thus m < n, or we can also say n \ge 2. Since R^n = R^{n-1} \circ R, it follows that there must exist an element b \in A such that (a,b) \in R and (b,c) \in R^{n-1}. Since (a,b) \in R, it follows d(a,b) = 1. Clearly by the definition of d(b,c), we can say that d(b,c) \le n-1. We will prove by contradiction that d(b,c) = n-1. Suppose k = d(b,c) < n-1. Thus (b,c) \in R^k. Since (a,b) \in R and (b,c) \in R^k, it follows that (a,c) \in R^{k+1}. Since k < n-1, it follows that k+1 < n. But this contradicts with the assumption that d(a,c) = n. It follows that k = d(b,c) = n-1 = d(a,c) - 1. Thus d(a,b) = 1 and d(b,c) = d(a,c) - 1. • Induction Step: Suppose theorem is true for m. Thus if m < d(a,c), it follows that \exists b \in A(d(a,b) = m \text{ and } d(b,c) = d(a,c) - m). Now consider for m+1. Suppose m+1 < d(a,c). Since m+1 < d(a,c), it follows m < d(a,c). Thus by induction hypothesis there exists an element b such that d(a,b) = m and d(b,c) = d(a,c) - m. Suppose n = d(a,c). Clearly (a,b) \in R^m and (a,c) \in R^n and (b,c) \in R^{n-m}. Since m+1 < n, it follows that n-m > 1. Thus R^{n-m} = R^{n-m-1} \circ R. Since (b,c) \in R^{n-m}, it follows that there exists an element b' such that (b',c) \in R^{n-m-1} and (b,b') \in R. Since (b,b') \in R, it follows d(b,b') = 1. Also by the definition of d(b',c), we can say that d(b',c) \le n-m-1. We will prove by contradiction that d(b',c) = n-m-1. Suppose k = d(b',c) < n-m-1. Since (b,b') \in R and (b',c) \in R^k, it follows (b,c) \in R^{k+1}. Since d(b,c) = n-m, it follows n-m < k+1, or n-m-1 < k. Thus we have a contradiction. It follows that d(b',c) = n-m-1. Since (a,b) \in R^m and (b,b') \in R, it follows that (a,b') \in R \circ R^{m} = R^{m+1}. Thus d(a,b') \le m+1. We shall prove by contradiction that d(a,b') = m+1. Suppose k = d(a,b') < m+1. Thus (a,b') \in R^k. Since (a,b') \in R^k and (b',c) \in R^{n-m-1}, it follows that (a,c) \in R^{n-m-1+k}. Since d(a,c) = n, it follows n < n-m-1+k, or m+1 < k. Thus we have a contradiction. It follows that d(a,b') = m+1. Thus we have an element b' such that d(a,b') = m+1 and d(b',c) = n-m-1 = d(a,c) - m - 1. Soln10 (a) Suppose S_n = \{ (a,b) \in A \times A \; \vert \; \text{there is an } R \text{-path form } a \text{ to } b \text{ of length } n \}. Thus we need to prove R^n = S_n. We can prove this by proving R^n \subseteq S_n and S_n \subseteq R^n. We shall prove this by induction. • Base Case: For n = 1, we need to prove R^1 \subseteq S_1 and S_1 \subseteq R^1. (\to) Suppose (a,b) \in R^1. Thus (a,b) \in R. Suppose that f = \{ (0,a), (1,b) \}. It follows that (f(0),f(0+1)) \in R. Thus f(0) = a, f(1) = b and \forall i < n((f(i),f(i+1)) \in R). Thus there is an R-path from a to b of length 1. Thus (a,b) \in S_1. Since (a,b) is arbitrary, it follows that R^1 \subseteq S_1. (\leftarrow) Suppose (a,b) \in S_1. Thus f(0) = a, f(1) = b and (f(0),f(1)) \in R. Thus (a,b) \in R, or (a,b) \in R^1. Since (a,b) is arbitrary, it follows that S_1 \subseteq R^1. • Induction Step: Suppose for n, R^n = S_n. Now lets consider of n+1. (\to) Suppose (a,c) \in R^{n+1}. Thus there exist an element b such that (a,b) \in R^n and (b,c) \in R. Since (a,b) \in R^n, then by induction hypothesis, (a,b) \in S_n. Thus there is an R-path from a to b of length n. It follows that f(0) = a, f(n) = b and \forall i < n((f(i),f(i+1)) \in R). Suppose f(n+1) = c. Since f(n) = b and (b,c) \in R, it follows that (f(n),f(n+1)) \in R. Thus \forall i < n+1 ((f(i),f(i+1)) \in R). Thus (a,c) \in S_{n+1}. Thus R^{n+1} \subseteq S_{n+1}. (\leftarrow) Suppose (a,c) \in S_{n+1}. It follows that f(0) = a, f(n+1) = c and \forall i < n+1 ((f(i),f(i+1)) \in R). Suppose f(n) = b. Since (f(n),f(n+1)) \in R, it follows that (b,c) \in R. Since \forall i < n+1 ((f(i),f(i+1)) \in R), we can also say \forall i < n ((f(i),f(i+1)) \in R). Since f(0) = a and f(n) = b, it follows that (a,b) \in S_n. Thus by induction hypothesis, it follows (a,b) \in R^n. Since (a,b) \in R^n and (b,c) \in R, it follows that (a,c) \in R^{n+1}. Thus S_{n+1} \subseteq R^{n+1}. (b) We know from theorem 6.5.2, S = \cup_{n \in Z^+} R^n. Suppose P = \{ (a,b) \in A \times A \; \vert \; \text{there is an } R \text{-path form } a \text{ to } b \}. Thus we need to prove S = P. Suppose P_n = \{ (a,b) \in A \times A \; \vert \; \text{there is an } R \text{-path form } a \text{ to } b \text{ of length } n \}. Clearly P = \cup_{i \in Z^+}P_n. Suppose n is arbitrary positive integer. Thus from part(a) R^n = P_n. Since n was arbitrary, it follows that \cup_{i \in Z^+} R^n = \cup_{i \in Z^+}P_n. Thus S = P. Soln11 (a) Suppose S_n = \{ (a,b) \in A \times A \; \vert \; \text{there is a "simple" } R \text{-path form } a \text{ to } b \text{ of length at most } n \}. We will prove this by induction. • Base Case: For n = 1. Suppose (a,b) \in R \setminus i_A. Thus (a,b) \in R and (a,b) \notin i_A. It follows that a \ne b. Suppose f = \{ (0,a), (1,b) \}. Thus f(0) = a, and f(1) = b and \forall i < 1 ( ( f(i),f(i+1) ) \in R). Since a \ne b, it follows f(0) \ne f(1). Thus f is one-to-one. Thus (a,b) \in S_1. It follows that R \setminus i_A \subseteq S_1, or R^1 \setminus i_A \subseteq S_1. • Induction Step: Suppose theorem is correct for n. Thus R^n \setminus i_A \subseteq S_n. Now consider for n+1. Suppose (a,c) \in R_{n+1} \setminus i_A. Thus a \ne c. Also it follows that there exist some element b such that (a,b) \in R^n and (b,c) \in R and a \ne b and$$ b \ne c $. Note: It can be easily proved by contradiction that$a \ne b$and$b \ne c$. I skipped it. Thus$(a,b) \in R_n \setminus i_A$and$(b,c) \in R \setminus i_A$. Thus by induction hypothesis, it follows$(a,b) \in S_n$. Thus there is a function$f$such that for some$m \le n$,$f(0) = a$and$f(m) = b$and$\forall i < m(f(i),f(i+1)) \in R$. We have following possible cases: • Case$c \in Ran(f)$: Suppose$f(k) = c$. Suppose$h$is a function such that$\forall i \le k (h(i) = f(i))$. Since$f$is one-to-one, it follows that$h$is$R$-path from$a$to$c$of length less than equal$n+1$. Thus$(a,c) \in S_{n+1}$. • Case$c \notin Ran(f)$: We have$f(0) = a$and$f(m) = b$where$m \le n$. Suppose$h$is a function such that$\forall i \le m(h(i) = f(i))$and$h(m+1) = c$. Thus$h(m) = f(m) = b$and$h(m+1) = c$. Since$(b,c) \in R$, it follows that$(h(m),h(m+1)) \in R$. Since$f$is one-to-one, we can say that$h$is a one-to-one function from$a$to$c$of length$m + 1$. Since$m \le n$, it follows that$m+1 \le n+1$. It follows that$(a,c) \in S_{n+1}$. Thus from both cases$(a,c) \in S_{n+1}$. Thus$R_{n+1} \subseteq S_{n+1}$if$R_n \subseteq S_n$. Thus$R_n \subseteq S_n$. (b) We know from theorem 6.5.2,$S = \cup_{n \in Z^+} R^n$. Suppose$P = \{ (a,b) \in A \times A \; \vert \; \text{there is a "simple" } R \text{-path form } a \text{ to } b \}$. We need to prove$S \setminus i_A = P$. ($\to$) Suppose$(a,b) \in S \setminus i_A$. Thus for some natural number$n$,$(a,b) \in R^n$such that$a \ne b$. Thus it follows from part(a) of this solution that$(a,b) \in P$. Thus$S \setminus i_A \; \subseteq \; P$. ($\leftarrow$) Suppose$(a,b) \in P$. Thus there exist a one-to-one function$f$such that for some natural number$n$,$f(0) = a$,$f(n) = b$and$\forall i < n((f(i),f(i+1)) \in R)$. Thus from Ex-10 part(a), it follows that$(a,b) \in R^n$. Thus$(a,b) \in S$. Since$f$is one-to-one, it follows$f(0) \ne f(n)$, or$a \ne b$. Thus$(a,b) \notin i_A$. Thus we can conclude$(a,b) \in S \setminus i_A$. Soln12 (a) Suppose$d(a,b) = n$and$a \ne b$. It follows that$(a,b) \in R^n \setminus i_A$. Thus from Ex-11 part(a), it follows that there exist a simple$R-$path of length at most$n$. We will prove by contradiction that length of path is$n$. Suppose length of$R$-path is$m$such that$m < n$. It follows that there is a one-to-one function$f$such that$f(0) = a$and$f(m) = b$, and$\forall i < m((f(i),f(i+1) \in R)$. Thus from Ex-10 part(a), it follows that$(a,b) \in R^m$. Since$n = d(a,b)$, it follows that$n \le m$. But it contradicts with assumption that$m < n$. Thus$m = n$. Thus there is a simple path from$a$to$b$of length$n$. (b) Suppose$d(a, a) = n$. We have following possible cases: • Case$n = 1$. Thus$(a,a) \in R$. Suppose$f = \{ (0,a), (1,a) \}$. Thus$f(0) = f(1) = a$. Also the statementt$\forall i < n \forall j < n(f(i)= f(j) \to i = j)$is vacuously true. • Case$n > 1$. Thus$(a,a) \in R^n$. Suppose$m = n-1$. Since$m < n$, it follows from Ex-9 (b), there exist an element$b$such that$d(a,b) = m$and$d(b,a) = d(a,a) - m$. Thus$d(b,a) = n - (n-1) = 1$. It follows that$(b,a) \in R$. Now we shall prove that$a \ne b$by contradiction. Suppose$a = b$. Since$d(a,b) = n-1$, it follows$d(a,a) = n-1$. But$d(a,a) = n$. Thus we have a contradiction. It follows that$a \ne b$. Thus we have$d(a,b) = n-1$and$a \ne b$. Thus by part(a) of this solution it follows that there is a simple path from$a$to$b$of length$n-1$. Thus there is a one-to-one function$f$such that$\forall i < n-1( (f(i),f(i+1)) \in R)$. Suppose$f' = f \cup \{ (n,a) \}$. Since$(b,c) \in R$, it follows$(f'(n-1),f'(n)) \in R$Since$f$is simple path, it follows that$\forall i and $f'(0) = f'(n) = a$.

Thus $f'$ is a simple path except $f'(0) = f'(n) = a$.

Soln13

Suppose $f :J_n \to A$ is a simple $R$-path from $a$ to $b$ of length $n$, where $J_n = \{0,1,2, ... n\}$.

Clearly length of path is $n$ and $J_n$ contains $n+1$ elements.(using the same definition as defined in book).

Since $A$ contains $m$ elements and $f$ is one-to-one, it follows that $J_n$ can contain at max $m$ elements.

It follows that maximum length of $f$ is $m-1$.

Suppose $(a,b) \in S$. Suppose that $d(a,b) = n$. Consider the following cases:

• Case $a \ne b$

Since maximum length of a simple $R$-path is $m-1$, then from Ex-12 part(a), it follows that $d(a,b) \le m - 1$. Thus $(a,b) \in R^{n}$ where $1 \le n \le m-1$. It follows that $(a,b) \in \cup \{ R^n \, \vert \, 1 \le n \le m-1 \}$.

• Case $a = b$

Using the result of Ex-12(b), it follows maximum length of such path is $\text{ maximum length of simple path } + 1 = m - 1 + 1 = m$. Thus $(a,b) \in R^{n}$ where $1 \le n \le m$. It follows that $(a,b) \in \cup \{ R^n \, \vert \, 1 \le n \le m \}$.

Thus combining both cases, it follows that $(a,b) \in \cup \{ R_n \, \vert \, 1 \le n \le m \}$.

It follows that $S \subseteq \cup \{ R^n \, \vert \, 1 \le n \le m \}$.

Also since $S = \cup_{i \in Z^+} R^n$, it follows that $\cup \{ R^n \, \vert \, 1 \le n \le m \} \subseteq S$.

Thus $S = \cup \{ R^n \, \vert \, 1 \le n \le m \}$.

Soln14

Earlier I tried this using induction on $i$ and not able to do it. Later it seems like it was wrong to apply induction on $i$ as value of $i$ is dependent on $n$.

We have to prove $\forall n \in \mathbb Z^+( 0 \le i \le n-1 \to (2+i) \; \vert \; (x+i) )$, where $x = (n+1)! + 2$.

We shall use induction on $n$.

• Base Case:

For $n = 1$. Thus the only possible value of $i = 0$. Thus $x+i = (1+1)! + 2 = 4$. And $2+i = 2$. Thus $(2+i) \; \vert \; (x+i)$.

• Induction Step:

Suppose for $n$, $(2+i) \; \vert \; (x+i)$. Thus for some integer $k$, $k(2+i) = (n+1)! + 2 + i$.

Now consider for $n+1$,

Thus for $n+1$:
Value of $i$ will be $0 \le i \le n+1-1$. Thus $0 \le i \le n$. And $x+i = (n+1+1)! + 2 + i = (n+2)! + 2 + i$.

Consider the following cases:

• Case $i = n$:

Thus $x+i = (n+2)! + 2 + n = (n+2)((n+1)! + 1)$. Thus $2+i = 2+n$ divides $x+i$.

• Case $0 \le i \le n-1$:

Since $0 \le i \le n-1$, thus by induction hypothesis, it follows that $k(2+i) = (n+1)! + 2 + i$. Thus $(2+i)(k-1) = (n+1)!$.

Thus $x + i = (n+2)! + 2 + i = (n+2)(n+1)! + 2 + i = (n+2)(2+i)(k-1) + 2 + i$. Thus $x+i = (2+i)((n+2)(k-1) + 1)$. Thus $(2+i) \; \vert \; (x+i)$.

Thus in both cases $(2+i) \; \vert \; (x+i)$.