Problem involving set and relations

[nistaria]

First this is my first attempt at using latex to ask a question, so my appologies if the statements come out strange. I'll edit as needed.

Homework Statement

Let R and S be relations on a set A. Prove that if R \subseteq S, then R^{n} \subseteq S^{n} for all n \geq 1

Homework Equations

n/a

The Attempt at a Solution

I used proof by induction.

Base case:
Let n=1 thenR \subseteq S, thenR^{n} \subseteq S^{n} =R^{1} \subseteq S^{1} which is equal to R \subseteq Swhich is true.

Inductive step:
Suppose that R^{k} \subseteq S^{k}forn=kand [/tex]k \geq 1[\tex]
We need to show that R^{k+1} \subseteq S^{k+1}is true as well.
R^{k+1} \subseteq S^{k+1} = R \circ R^{k} \subseteq S \circ S^{k}

ok, so here goes. I'm lost at this point. I know that for instance, if (a,b) are elements of Rⁿ then it must be the case that (a,b) are elements of Sⁿ

Any help, prefferably hints as I'd rather learn then get complete solutions handed to me would be greatly appreciated.
Thanks for reading

 

[tiny-tim]

hi nistaria!

your induction proof needs to begin "if (a,b) ε Rⁿ⁺¹, then there is a c such that …"