If $R$ is transitive and $S$ is reflexive, Prove $(R\ ; S\ ;R)^2 \subseteq (R\ ;S)^3$

Question

$ R $ and $S$ are two relations.

Given $R$ is transitive and $S$ is reflexive

How can I Prove $(R\ ; S\ ;R)^2 \subseteq (R\ ;S)^3$

Can you tell me what the notation $(R;S;R)$ and $(R;S)$ means? — Patrick Da Silva, Oct 30 '15 at 10:22

score 3 · Accepted Answer · edited Oct 30 '15 at 10:18

3

We have, by associativity, that $$ (R;S;R)^2 = R;S;R;R;S;R = R;S;R^2;S;R $$ Now, as $R$ is transitive, $R^2\subseteq R$, hence $$ (R;S;R)^2 \subseteq R;S;R;S;R $$ As $S$ is reflexive $\operatorname{id}\subseteq S$, giving $$ (R;S;R)^2 \subseteq R;S;R;S;R = R;S;R;S;R;\operatorname{id} \subseteq R;S;R;S;R;S = (R;S)^3 $$

edited Oct 30 '15 at 10:18

Ben Millwood

14,211

answered Oct 30 '15 at 10:13

martini

84,101

Thank you for your answer ! – TechJ Oct 30 '15 at 10:28
can you just explain that as $S$ is reflexive then why we consider $Id \subseteq S$ – TechJ Nov 02 '15 at 15:21

If $R$ is transitive and $S$ is reflexive, Prove $(R\ ; S\ ;R)^2 \subseteq (R\ ;S)^3$

1 Answers1