0
$\begingroup$

Choose the transitive closure of the relation R={(a,b),(b,a),(b,c),(c,d),(c,e)}

My answer was

(a,c),(b,d),(a,d),(b,e),(a,e)

But it was wrong. The correct answer was:

R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,a),(b,b),(b,c),(b,d),(b,e),(c,d),(c,e)}

I do not understand why pairs such as (a,a) is needed in a transitive closure, isn't that a reflexive closure? I also do not get why the same pairs was added, like (a,b) when it was already in the relation before the closure (perhaps this is just to show the full relation after the closure).

$\endgroup$
1
$\begingroup$

This is because $(a,b)$ and $(b,a)$ is in your relation that is $(a,b)$ gives us that $a$ is related to $b$ and $(b,a)$ gives us that $b$ is related to $a$. So for transitivity $a$ should be related to $a$ that is $(a,a)$ should be there.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer :) $\endgroup$ – user504783 Dec 4 '17 at 17:51
0
$\begingroup$

The closure og R always contains R. You need to iteratively add pairs to R by taking two existing ones with the form (r,s) and (s,t) and then add (r,t) if it isn't there already. I.e. since you have (a,b) and (b,a) you must add (a,a).

$\endgroup$
1
  • $\begingroup$ Thanks for the answer :) $\endgroup$ – user504783 Dec 4 '17 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy