Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 6 / b / v / Solution

The answer is no, even when both original binary relations are equivalence relations. On $X=\{a,b,c\}$, let $R_1$ have equivalence classes $\{a,b\},\{c\}$ and $R_2$ have equivalence classes $\{a\},\{b,c\}$. Each is a transitive relation and, by the earlier proof, a Euclidean relation.

Use exactly the paper's convention for composition of relations: $xRy$ means $x{R}_{1}z$ and $z{R}_{2}y$ for some $z$. The possible successors areIndeed, from $a$ or $b$ the first step can reach $a$ or $b$, whose $R_2$ successors together exhaust $X$; from $c$ the first step must stay at $c$, whose $R_2$ successors are only $b,c$. Consequently $cRb$ and $bRa$, but not $cRa$. Therefore