 Solution

ID: 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

x R y

. Reflexivity gives

x R x

, so applying the Euclidean implication to

x R y

and

x R x

gives

y R x

To prove it is a transitive relation, assume

x R y

and

y R z

. The symmetry just established gives

y R x

. Apply the Euclidean implication with common predecessor

y

y R x

and

y R z

x R z

. Thus all three requirements hold:

R reflexive and Euclidean ⟹ R an equivalence relation .

 New to topics? Read the docs here!