2
$\begingroup$

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$.

Partial answer of mine:

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Parham Nov 7 '13 at 13:26
  • $\begingroup$ 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$? $\endgroup$ – Yuval Filmus Nov 8 '13 at 6:47
2
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

This is best carried out using notations from algebra of relations.

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$

as required.

$\endgroup$
  • $\begingroup$ Hmm, we have not had a single piece of this on university as far as I can recall. But I get the idea sort of. $\endgroup$ – skiwi Nov 8 '13 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.