Timeline for Calculate transitive closure of a relation
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 30, 2015 at 13:17 | vote | accept | Nubcake | ||
| Apr 30, 2015 at 13:14 | comment | added | j4GGy | One thing to take away from this is that transitivity is quite a strong property. That means that "making a set transitive" usually makes it much "bigger". A nice way to work out the transitive closure is using graphs as you stated. Just draw a vertex for each element of the "basis set" (here: $1,2,3,4$) and draw an arrow from $a$ to $b$ if $(a,b) \in R$. Now, whenever you see an arrow from $a$ to $b$ and from $b$ to $c$, just add an arrow from $a$ to $c$. This way you eventually get the transitive closure. | |
| Apr 30, 2015 at 13:11 | comment | added | Nubcake | Ok I think I understand it now, just wondering how I managed to arrive with more than 10 pairs when computing the transitive closure? How did you manage to work it out ? It seems for this case that it is just the reflexive set of R union with R. | |
| Apr 30, 2015 at 13:05 | comment | added | j4GGy | @Nubcake You're right - we're still missing $(3,3)$ and $(4,4)$, my bad. So for $R = \{(1,3),(3,1),(2,4),(4,2)\}$ the transitive closure is $R^+ = \{(1,1),(2,2),(3,3),(4,4), (1,3),(3,1),(2,4),(4,2)\}$. Sorry, if my mistake confused you. However, to comment on your earlier question: There should be no compositions $\circ$ in the answer given in your book/exercise. They are meant to be unions $\cup$. | |
| Apr 30, 2015 at 13:01 | comment | added | Nubcake | {(1,3),(2,4),(3,1),(4,2)} is the answer I got after computing all the compositions that the answer provided me with. So which answer is wrong? Why is {(1,3),(2,4),(3,1),(4,2),(1,1),(2,2)} the transitive closure? This set is not transitive. | |
| Apr 30, 2015 at 12:57 | comment | added | j4GGy | For the example in your question it actually is the set of all possible pairs (as stated in my answer). For the set you mentioned in the comments, it is not the set of all pairs and the process of adding pairs will stop after you added $(1,1)$ and $(2,2)$. | |
| Apr 30, 2015 at 12:55 | comment | added | Nubcake | But if I keep on adding pairs like I was doing before, I would end up with a set containing all possible pairs of A x A? That wouldn't be the transitive closure of the set then would it? Also , (3,3) is also missing right? Why didn't the answer given the "transitive closure" then? Sorry but I'm still confused , why is R+ transitive? We are missing quite a lot of pairs. It's turning out like we need to add all possible pairs to make it transitive. | |
| Apr 30, 2015 at 12:52 | comment | added | j4GGy | @drhab actually I meant "is not transitive" - seems my mind wandered off for a sec there :) | |
| Apr 30, 2015 at 12:51 | comment | added | drhab | @GenericNickname You meant to say "is not reflexive" | |
| Apr 30, 2015 at 12:47 | comment | added | j4GGy | Unfortunately there is no very efficient way other than to add pairs iteratively. However, your example is very nice. The set $\{(1,3),(2,4),(3,1),(4,2)\}$ is not relative because it is missing $(1,1),(2,2)$. However, if we add those pairs, we arrive at the transitive closure $\{(1,3),(2,4),(3,1),(4,2),(1,1),(2,2)\}$ | |
| Apr 30, 2015 at 12:37 | comment | added | Nubcake | So what is the quickest way to compute the transitive closure , I am still unsure approaching this even though I've read your answer. Yes I also saw in notes before that the maximum possible number of pairs would we have to possibly add would be the cardinality of the set. I think I am confusing myself now; is {(1,3),(2,4),(3,1),(4,2)} transitive? We are missing (1,1) and (2,2)... | |
| Apr 30, 2015 at 12:30 | history | edited | j4GGy | CC BY-SA 3.0 |
added 15 characters in body
|
| Apr 30, 2015 at 12:23 | history | answered | j4GGy | CC BY-SA 3.0 |