Proof by induction in Relations

Question

$R$ and $S$ be relations such that $R\subseteq S$. Prove that $R^n \subseteq S^n$ for all positive integers.Can anyone help me in proving this using induction?

Answer 1

So your base case, $n = 1$ is easy.

Say $R^n \subseteq S^n$. You want to show that if $R^{n+1} \subseteq S^{n+1}$. Pick an $(x,y) \in R^{n+1}$. By the definition of $R^{n+1}$, there is a $z$ such that $(x,z) \in R^n$ and $(z,y) \in R$. Now use your induction hypothesis.

(I assumed your definition of $R^n$ is composition, not $n$-ary, because frankly, what you said doesn't make sense)