Proof: If $R\subseteq S$ then $R^*\subseteq S^*,$ which $R,S$ are relations.

Question

I don't know how to start the proof. How to show because any path in $R$ is also a path in $S$ mathematically?

--

Definition of $R^n$

Definition of path

Answer 1

Suppose $S$ is a transitive relation. Then $S^2\subseteq S$ by definition of transitivity. Therefore, by induction, $S^n\subseteq S$: suppose $S^k\subseteq S$; then $$ S^{k+1}=S^k\circ S\subseteq S\circ S\subseteq S $$ Therefore $S^*=S$.

Next we want to show that if $R\subseteq S$ (any relations), then $R^*\subseteq S^*$. This follows from a more general result: if $A$, $B$, $C$, $D$ are relations with $A\subseteq C$ and $B\subseteq D$, then $A\circ B\subseteq C\circ D$ (prove this). Then prove, by induction, that $R\subseteq S$ implies $R^n\subseteq S^n$. Passing to the unions, we conclude $R^*\subseteq S^*$.

Last lemma: $R^{m}\circ R^{n}=R^{m+n}$ (proof by induction on $n$).

Now, the transitive closure of $R$ is the intersection of all transitive relations containing $R$. In order to show that $R^*$ is the transitive closure of $R$, you need to show:

1. $R^*$ is transitive
2. If $R\subseteq S$ and $S$ is transitive, then $R^*\subseteq S$.

The second property follows from what said before: if $R\subseteq S$, then $R^*\subseteq S^*$, but as $S$ is transitive, $S^*=S$.

The transitivity of $R^*$ is proved as follows: suppose $(a,b),(b,c)\in R^*$. Then for some $m$ and $n$, $(a,b)\in R^m$ and $(b,c)\in R^n$. Therefore $(a,c)\in R^{m+n}$, so $(a,c)\in R^*$.

---

What's the text saying about paths? If $(a,b)\in R^n$, by the very definition there are $x_1,x_2,\dots,x_{n-1}$ such that $$ (a,x_1)\in R,\quad(x_1,x_2)\in R,\quad\dots,\quad (x_{n-2},x_{n-1})\in R,\quad (x_{n-1},b)\in R $$ This is a path in $R$ interpreted as a directed graph. If $R\subseteq S$, then every path in $R$ is obviously a path in $S$.

Answer 2

First, you did not explain the notations in what you posted: what is $R^n$ for a relation? What is a path?

Let me guess a path of length $n$ is a sequence $(a_0,a_1),(a_1,a_2),...,(a_{n-1},a_n)$ such that $(a_i,a_{i+1})\in R$ for all $i=0,\dots,n-1$. Then I guess $R^n$ is the set form by the $(a_0,a_n)$ for the initial $a_0$ and terminal $a_n$ elements of paths of length $n$.

Now, if $R\subset S$, then $R^n\subset S^n$ clearly, hence $R^*\subset S^*$, which by definition is the union of all $R^n$.