Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Discrete mathematics, continuous mathematics and probability / 1 / e

Use the convention that $R\circ S$ applies $S$ first. Reflexivity inserts an identity step: if $aRb$, use $aSa$ to obtain $(a,b)\in R\circ S$; if $aSb$, use $bRb$ for the same conclusion. Thus $R\cup S\subseteq R\circ S$. By monotonicity of relation composition,For strictness, take $A=\{0,1,2,3\}$ and let $R=S$ consist of the identity pairs together with $(0,1),(1,2),(2,3)$. Both are reflexive relations. The left side permits at most two forward chain steps, so does not contain $(0,3)$. The right side permits four steps, including $0\to 1\to 2\to 3\to 3$, so does contain it. Equality therefore need not hold.