Prove that a transitive relation can be "shortcutted"

Question

I want to prove the following theorem and already spent a lot of time on doing this, but almost unsuccessfully:

Let $R$ be a transitive relation over the set $A$. Prove that in the graphical representation of the relation (that is, the graph $(A, R)$), that $(u, v) \in R$ if $v$ is reachable from $u$.

So, reachability here I think means that there is a path from $u$ to $v$. What I tried so far:

1. I tried to prove that "$v$ is reachable from $u$ $\implies uRv$" using contradiction that $u \not R v$. I thought that if there is a path, then we can find some $x$, where $uRx$, but $x \not R v$, otherwise it would mean that $uRv$. And this led me to the conclusion that it must be at least one more point between $x$ and $v$ and so on ad infinitum.
2. Another attempt was hiring contrapositive with further contradiction (if $u \not R v \implies v$ is not reachable from $u$. Then for the sake of contradiction assuming that there is a path between $u$ and $v$). But this also led me to the same result as the first one.
3. Since the first and the second attempts led me to an "endless" path between $u$ and $v$ I thought that induction can be a solution here. First of all, let's assume that any set, constructed of the elements of the path $uRx_1, x_1Rx_2, ..., x_nRv$ have the greatest element in respect to $R$. (I will prove it if my proof of the original theorem is correct). So let $P(n)$ is true when "if there is $n$-length path between $u$ and $v$, then $uRv$" is true. I'm not sure but it seems that $P(0)$ is true, because there is always a zero-path between any elements. Let's consider any $n+1$-length path and remove the greatest element $x_{n+1}$ from it. The resulting path has length $n$, so that we sure know that $uRx_n$. Now put the $x_{n+1}$ back and since we know that $x_{n + 1}$ is the greatest it means that $x_{n} R x_{n+1}$. Then by transitivity we have that $uRx_{n+1}$.

UPDATE:

First of all, let's assume that any set, constructed of the elements of the path $uRx_1, x_1Rx_2, ..., x_nRv$ have the greatest element in respect to $R$

Now I think that this lemma above is another way to prove the theorem. So if I proved it, I could prove that the greatest element is $v$ and then we would have $uRv$.

I'm sorry for a lot of text, but I'd like you to look at all my attempts and, probably, suggest how I can improve all of them to prove the theorem (if this is possible). So does my induction hypothesis seem good or is there a better one for this theorem? Is it correct to say that $P(0)$ is true?

And could you please provide any hints how this theorem can be proved without induction (like I tried in my first and second attempts) if this is possible? I'd be also grateful if you can criticize my conclusions and assumptions.

Answer 1

Your attempts 1 and 2 are just two different ways to present essentially the same proof.

The logical form of attempt 1 is: you suppose that "$v$ is reachable from $u$" and "$u \, \not R \, v$", then you show that these assumptions lead to conclude "$v$ is not reachable from $u$", which gives you a contradiction with your first assumption. Hence, if you suppose that "$v$ is reachable from $u$" then "$u \, R \, v$".

The logical form of attempt 2 is: you suppose that "$u \, \not R \, v$", then you show that this assumption leads to conclude "$v$ is not reachable from $u$". According to a well-known result in logic, this amounts to say if you suppose that "$v$ is reachable from $u$" then "$u \, R \, v$".

The problem in your attempts 1 and 2 is that it is not clear at all how you conclude that "$v$ is not reachable from $u$". What you sketched seems to suggest that there is an arbitrarily long finite path (or maybe an infinite path) from $u$ to $v$, but this is not enough to conclude because it does not exclude the possibility that there is a finite path from $u$ to $v$ and so that $v$ is reachable from $u$.

---

The hypothesis "$v$ is reachable from $u$" means that there is a path $u \, R \, x_1, \, x_1 \, R \, x_2, \dots, \, x_n \, R \, v$ for some $n \in \mathbb{N}$; we say that the length of such a path is $n+1$ (in particular, if $n = 0$ then the length of the path is $1$). So, your hypothesis says that there is a path of length $k > 0$ from $u$ to $v$, but you don't know the value of $k$. It is then natural to prove that $u \, R \, v$ by showing that, for whatever length greater than $0$ of the path from $u$ to $v$, we have $u \, R \, v$.

When you want to prove that a property holds for all natural numbers, or for all natural numbers greater than some $m$, the usual rigorous way to proceed is by induction. Any other proof of that property would be either hand-waving and not rigorous, or based on other lemmas proved by induction.

Formally, we want to prove that "for any natural number $k > 0$, $P(k)$ holds", where $P(k)$ is:

"if there is a path from $u$ to $v$ of length $k$, then $u \, R \, v$."

Let us prove it by induction on $k > 0$. We have to prove the base case and the induction step.

Base case. For $k = 1$, the assumption "there is a path from $u$ to $v$ of length $1$" means that $u \, R \, x_1, \, x_1 \, R \, x_2, \dots, \, x_n \, R \, v$ for $n = 0$, i.e. $u \, R \, v$, which is exactly what we want to prove.

Inductive step. Let us fix $k > 0$ and suppose that $P(k)$ holds, i.e. "if there is a path from $u$ to $v$ of length $k$, then $u \, R \, v$": this is our induction hypothesis. We want to prove that $P(k+1)$ holds. Thus, we suppose that there is a path from $u$ to $v$ of length $k+1$. This means that $u \, R \, x_1, \, x_1 \, R \, x_2, \dots, \, x_k \, R \, v$. In particular, $u \, R \, x_1, \, x_1 \, R \, x_2, \dots, x_{k-1} \, R \, x_{k}$, which is a path of length $k$ from $u$ to $x_{k}$. By the induction hypothesis, $u \, R \, x_{k}$. From transitivity of $R$, since $u \, R \, x_{k}$ and $x_{k} \, R \, v$, it follows that $u \, R \, v$.

---

A final remark about your attempt 3. It is not clear what is the meaning of your "lemma", or the way you use it in your attempt 3. Your lemma says:

First of all, let's assume that any set, constructed of the elements of the path $uRx_1, x_1Rx_2, ..., x_nRv$ have the greatest element in respect to $R$.

It does not say anything about who is the greatest element (moreover, how can you be sure that there is the greatest element? Are you sure that $R$ is an order relation?). But in your attempt 3 you assume that last element of the path is the greatest element. You didn't prove that this further assumption is true and actually is false: $R$ might be a cyclic relation, for instance $u \, R \, x_1, \, x_1 \, R \, x_2, \, x_2 \, R \, v$ with $v = x_1 \neq x_2$.

Anyway, your attempt of proof by induction relies on a good intuition. You just have to pay more attention to details and to be more rigorous. This is why I wrote a quite verbose proof by induction.

Answer 2

Induction is indeed the way to go; here is one way to carry it out nicely. Suppose that $v$ is reachable from $u$, and let $u=w_0,w_1,\ldots,w_n=v$ be a path from $u$ to $v$. By hypothesis $w_0\,R\,w_1$. Suppose that $w_0\,R\,w_k$ for some $k$ with $1\le k<n$. By hypothesis $w_k\,R\,w_{k+1}$, so by transitivity we have $w_0\,R\,w_{k+1}$. By induction it follows that $w_0\,R\,w_k$ for $k=1,\ldots,n$, and in particular that $u=w_0\,R\,w_n=v$.