Exercise 6.5.11 (Velleman's How to Prove It)

Question

Suppose
$R$ is a relation on set $A$.
$S$ is the transitive closure of $R$.
$\forall n \in \mathbb{Z}^+ (J_n = \{0,1,2,\dots, n\})$.

Let $a,b \in A$.
$f: J_n \rightarrow A$ is an $R$-path from $a$ to $b$ of length $n$ if $f(0)=a \land f(n)=b \land \forall i < n (f(i), f(i+1)) \in R$.
If, in addition, $f$ is one-to-one, the $R$-path is said to be simple.

Prove $\forall n \in \mathbb{Z}^+ (R^n \setminus i_A \subseteq \{ \exists \text{simple $R$-path from $a$ to $b$ of length $\leq n$}\})$
For convenience, let $S_n = \{ \exists \text{simple $R$-path from $a$ to $b$ of length $\leq n$}\}$.
So, we need to prove $\forall n \in \mathbb{Z}^+ (R^n \setminus i_A \subseteq S_n)$, where $i_A$ is the identity relation on $A$.

My attempt (using ordinary induction):
Base case: n=1.
Suppose arbitrary $(a,b) \in R^1 \setminus A$.
$(a,b) \in R \land (a,b) \notin i_A$, thus, $a \neq b$.
Let $f = \{(0,a), (1,b)\}$, then $f(0)=a \land f(n=1)=b \land \forall i < n=1 (f(i), f(i+1)) \in R$.
In addition, since $a \neq b$, $f$ is one-to-one, so, $f$ is a simple $R$-path from $a$ to $b$ of length $n$. Thus, $(a,b) \in S_1$.
Since $(a,b) \in R^1 \setminus A$ is arbitrary, $R^1 \setminus A \subseteq S_1$.

Induction step:
Suppose arbitrary $n \in \mathbb{Z}^+$.
Suppose $R^n \setminus i_A \subseteq S_n$. Need to show $R^{n+1} \setminus i_A \subseteq S_{n+1}$.
Suppose arbitrary $(a,c) \in R^{n+1} \setminus i_A$.
$(a,c) \in R^{n+1} \land (a,c) \notin i_A$, so, $a \neq c$, and
$\exists b \in A ( (a,b) \in R^n \land (b,c) \in R^1)$.
$\vdots$
This is where I stuck.

The solutions I found hinted that we can first prove that $a \neq b \land b \neq c$ to proceed. I tried proof by contradiction (by assuming $a=b \lor b=c$) but found nothing to contradict with.

So, my question now is how to show $a \neq b \land b \neq c$?

Answer 1

You can do this without induction.

Hint: Problem 10 shows that $(a,b)\in R^n$ iff there is an $R$-path of length $n$ from $a$ to $b$. (You would need induction to prove this.) So, given such a path, can you show that there is a simple $R$-path from $a$ to $b$ with length at most $n$?

Answer 2

Lemma: In exercise 10, it's shown that
$\forall n \in \mathbb{Z}^+ (R^n = \{ (a,b) \in A \times A \mid \text{$\exists$$R$-path from $a$ to $b$ of length $n$}\})$.

Theorem: $\forall n \in \mathbb{Z}^+ (R^n \setminus i_A \subseteq S_n)$.

Proof:
Suppose arbitrary $n \in \mathbb{Z}^+$.
Suppose arbitrary $(a,b) \in R^n \setminus i_A$.
$(a,b) \notin i_A \equiv a\neq b$.
From exercise 10, since $(a,b) \in R^n$, $\exists$$R$-path from $a$ to $b$ of length $n$.

Let $f: J_n \rightarrow A$ be the mentioned $R$-path. However, $f$ might not be one-to-one. There might be some $d\in A$ such that $\exists i<n ( f(i)=d, f(i+1)=d) \in R$.

Now that we have identified the $i$'s causing $f$ to be not one-to-one, we can remove every pair in $f$ containing those $i$'s as abscissa, re-index all the abscissas of the remaining pairs in increasing order of natural numbers (i.e. $0,1,2,\dots$) to form an one-to-one function $g: J_{k \leq n} \rightarrow A$. Notice this process preserves the properties of $g(0)=a \land g(k)=b \land \forall i<k (g(i), g(i+1)) \in R$. Thus, $g$ is considered a simple $R$-path from $a$ to $b$ of length $k \leq n$. This means $(a,b) \in S_n$.

Since $(a,b) \in R^n \setminus i_A$ is arbitrary, $R^n \setminus i_A \subseteq S_n$.
Since $n \in \mathbb{Z}^+$ is arbitrary, $\forall n \in \mathbb{Z}^+ (R^n \setminus i_A \subseteq S_n)$. $\blacksquare$

Example:
Let's see an example of the 'process' I mentioned in the proof above. Let's say we have $R = \{ (a,q), (q,q), (q,b)\}$. Then, since $(a,b) \in R^3$, by exercise 10, $\exists$$R$-path from $a$ to $b$ of length $n=3$. Evidently, $f = \{ (0,a), (1,q), (2,q), (3,b) \}$ is one possible such $R$-path, yet $f$ is not one-to-one. So this $R$-path is not simple. To make it simple, we identify the culprit $i$'s to be $1$ since $(f(1)=q, f(1+1)=q) \in R$. Removing the pair containing $1$ as abscissa, we are left with $\{ (0,a),(2,q), (3,b) \}$. Re-indexing the abscissa in accordance to increasing order of natural numbers, we have an one-to-one function $g = \{ (0,a),(1,q), (2,b) \}$. It's not hard to check that $g$ is a simple $R$-path from $a$ to $b$ of length $3-1 \leq n=3$. So, $(a,b) \in S_{n=3}$.

Answer 3

In induction step we assume that $$(a,c) \in R^{n+1}\setminus i_A \iff (a,c) \in R \circ R^n \land a \neq c,$$ so we can have some $b \in A$, such that $(a,b) \in R^n$ and $(b,c) \in R$.
Thus by the inductive hypothesis there is simple R-path of at most length n from a to b and simple R-path of at most length 1 from b to c. Therefore we can have the union of these R-paths as R-path from a to c of at most length n+1.
If $a=b \lor b=c$, then by the inductive hypothesis we still can have a simple R-path from a to c, but of length n. Since $n < n+1$ then our R-path meets requirement of being at most of length $n+1$.