# Prove that two different concatenations of relations are equivalent

I've had this question on my exam today and I couldn't figure it out, I would like to know the answer.

The question:

Given relations $$R$$, $$S$$ on a set $$U$$.

$$R$$ is transitive, $$S$$ is reflexive.

Prove that $$(R;S;R)^2$$ is a subset of $$(R;S)^3$$.

By using associativity you get an equivalent question of:

Prove that $$R;S;R;R;S;R \subseteq R;S;R;S;R;S$$.

By monotonicity you have that $$R;S;R \subseteq S;R;S$$.

Then I took $$(x, y) \in R;S;R$$, so there exist $$a, b \in U$$ such that $$xRa \land aSb \land bRy$$.

Now I need to conclude that $$xSa \land aRb \land bSy$$.

Here I am stuck, nowhere I see how I should be using that $$R$$ is transitive and $$S$$ is reflexive, and I know they are obvious hints. I tried using them directly, proving by contradiction, but I am just stuck.

• It should be "xSa' && aRb' && b'Sy" in the second composition. The same a and b may not work to conclude that. S is reflexive use this first to find a suitable pair a and b. Then apply transitivity of R to the first composition. Nov 7, 2013 at 13:26
• What do you mean by "$R;S;R \subseteq S;R;S$ by monotonicity"? What is monotonicity here? Why do you think it implies $R;S;R \subseteq S;R;S$? Nov 8, 2013 at 6:47

Here is an answer without using the algebra of relations (but otherwise identical to phs's). Suppose that $a(R;S;R)^2b$. Then there exist elements $c,d,e,f,g \in U$ such that $$aRc, cSd, dRe, eRf, fSg, gRb.$$ Since $R$ is transitive, $dRe$ and $eRf$ imply that $dRf$. Since $S$ is reflexive, $bSb$. Therefore $$aRc, cSd, dRf, fSg, gRb, bSb.$$ In other words, $a(R;S)^3b$.
You're asked to prove $RSRRSR \leq RSRSRS$. That $R$ is transitive means $RR\leq R$, so $RSRRSR \leq RSRSR$ by monotonicity of composition. That $S$ is reflexive means $I\leq S$, where $I$, the identity relation, is neutral element for composition: $I\leq S$ entails $(RSRSR)I\leq (RSRSR)S$ (monotonicity of composition again). Finally, you have
$(RSR)^2 = RSRRSR \leq RSRSR = RSRSRI \leq RSRSRS = (RS)^3$