How to Prove It - Solutions

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)$.