Q: Proof: If $R\subseteq S$ then $R^*\subseteq S^*,$ which $R,S$ are relations. 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


A: 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:


*

*$R^*$ is transitive

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

A: 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$. 
