- #1
nistaria
- 8
- 0
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.
Let R and S be relations on a set A. Prove that if [tex]R \subseteq S, then R^{n} \subseteq S^{n} for all n \geq 1[/tex]
n/a
I used proof by induction.
Base case:
Let [tex] n=1 [/tex] then[tex] R \subseteq S[/tex], then[tex] R^{n} \subseteq S^{n} =R^{1} \subseteq S^{1}[/tex] which is equal to [tex]R \subseteq S [/tex]which is true.
Inductive step:
Suppose that [tex]R^{k} \subseteq S^{k} [/tex]for[tex] n=k [/tex]and [/tex]k \geq 1[\tex]
We need to show that [tex]R^{k+1} \subseteq S^{k+1} [/tex]is true as well.
[tex] R^{k+1} \subseteq S^{k+1} = R \circ R^{k} \subseteq S \circ S^{k}[/tex]
ok, so here goes. I'm lost at this point. I know that for instance, if (a,b) are elements of Rn then it must be the case that (a,b) are elements of Sn
Any help, prefferably hints as I'd rather learn then get complete solutions handed to me would be greatly appreciated.
Thanks for reading
Homework Statement
Let R and S be relations on a set A. Prove that if [tex]R \subseteq S, then R^{n} \subseteq S^{n} for all n \geq 1[/tex]
Homework Equations
n/a
The Attempt at a Solution
I used proof by induction.
Base case:
Let [tex] n=1 [/tex] then[tex] R \subseteq S[/tex], then[tex] R^{n} \subseteq S^{n} =R^{1} \subseteq S^{1}[/tex] which is equal to [tex]R \subseteq S [/tex]which is true.
Inductive step:
Suppose that [tex]R^{k} \subseteq S^{k} [/tex]for[tex] n=k [/tex]and [/tex]k \geq 1[\tex]
We need to show that [tex]R^{k+1} \subseteq S^{k+1} [/tex]is true as well.
[tex] R^{k+1} \subseteq S^{k+1} = R \circ R^{k} \subseteq S \circ S^{k}[/tex]
ok, so here goes. I'm lost at this point. I know that for instance, if (a,b) are elements of Rn then it must be the case that (a,b) are elements of Sn
Any help, prefferably hints as I'd rather learn then get complete solutions handed to me would be greatly appreciated.
Thanks for reading