 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/v/solution

The answer is no, even when both original binary relations are equivalence relations. On

X = {a, b, c}

, let

R_{1}

{a, b}, {c}

and

R_{2}

{a}, {b, c}

Use exactly the paper's convention for composition of relations:

x R y

x R_{1} z

and

z R_{2} y

for some

z

. The possible successors are

R (a) = R (b) = {a, b, c}, R (c) = {b, c} .

Indeed, from

a

b

the first step can reach

a

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

c R b

and

b R a

, but not

c R a

. Therefore

R_{1} and R_{2} transitive and Euclidean does not force R transitive .

 New to topics? Read the docs here!