# 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. – Parham Nov 7 '13 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$? – Yuval Filmus Nov 8 '13 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$