i get trouble in one problem...
if we have relation R={(a,b), (b,c), (b,d), (c,e), (d,e), (c,f), (e,a)}, on set {a,b,c,d,e,f}. how many elements the transitive closure of R has?
I try google it, but I couldn't find any relation. anyone can help me ?
I know about relation, but this is a hard problem. everyone could help me ?
Recall that a relation is transitive if for all $a, b, c$ in $\{a, b, c, d, e, f\}$, if $(a, b)\in R$ and $(b, c) \in R$, then $(a, c) \in R$. Your job is to extend $R$ so that it is transitive.
You need to find, and add to the given set, all pairs $(x, z)$ for which $(x, y)\in R$ and $(y, z) \in R)$, if $(x, z)$ is not already in the set.
E.g., $(a, b) \in R$ and $(b, c) \in R$, so we need to add $(a,c)$, because it is not already in $R$. Call the new set, including all of $R$ plus any needed pairs for transitive closure, $R_t$.
Be careful to check if any newly added pairs to $R_t$ require additional pairs to be added. For example, in $R$, we have $(c, e)$ and $(e, a)$, so we have to add $(c, a)$. Once that is added, since $(b, c)$ is in the original $R$, and we added $(c, a)$, we also need then to add $(b, a)$ to the emerging set $R_t$.