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 / iii / Solution

Suppose $R$ is a reflexive relation and a Euclidean relation. To prove it is a symmetric relation, assume $xRy$. Reflexivity gives $xRx$, so applying the Euclidean implication to $xRy$ and $xRx$ gives $yRx$.

To prove it is a transitive relation, assume $xRy$ and $yRz$. The symmetry just established gives $yRx$. Apply the Euclidean implication with common predecessor $y$ to $yRx$ and $yRz$; the conclusion is $xRz$. Thus all three requirements hold: