Let $R$ and $S$ be relations. Assume $dom(R)=ran(S)$ and $R \circ S$ is single rooted. Prove $S$ is single rooted.

Question

The domain of $R$ being equal to the range of $S$ is really throwing me off. Not sure how to write out what that means in a useful way.

Answer 1

I assume 'single rooted' means 'injectivity', that is, $x\,S\,y\ \land\ x'\,S\,y\ \implies\ x=x'$.

Then, consider elements $x,x',y\ $ so that $x\,S\,y\ \land\ x'\,S\,y$.
By hypothesis, $y\in{\rm dom}(R)$, that is, there is a $z$ with $y\,R\,z$.

Finally, we get $x\,(R\circ S)\,z\ \land\ x'\,(R\circ S)\,z$, therefore $x=x'$ because $R\circ S$ is single rooted.

---

What might confuse you here, is the functional order of relation composition.
A usual way to make it more convenient but not to clash with the notation of function composition, is to simply introduce the relation order composition, usually denoted by semicolon [$;$]$\,$: $$S\,;R\ :=\ R\circ S$$

Writing the above with this reversed composition, we get $$x\,S\,y\ \land\ x'\,S\,y\ \implies\ x\,(S\,;R)\,z\ \land\ x'\,(S\,;R)\,z\ \implies\ x=x'\,.$$