connectivity relation to find the transitive closure

Question

Hello I am having difficulties with this question: Use connectivity relation to find the transitive closure of relation $R = \{(a, e),(b, a),(b, d),(c, d),(d, a),(d, c),(e, a),(e, b),(e, c),(e, e)\}$ on $\{a, b, c, d, e\}$.

If how you do this question is finding $R^2$ and $R^3$, I know how to do that. But i'm not sure if that is what this question is asking. If anyone can help that would be great! Thank you

Answer 1

I suspect that "Using the connectivity relation" to find the transitive closure is the following algorithm. Start with $T=\emptyset$ as a beggining of the transitive closure

1. Choose a letter (say, start with a)
2. See to which elements a are related in as first part, in this case we only have $(a,e)$ so $a$ is only related to $e$. Add all of these pairs to $T$
3. For each new element found in the previous step see which pairs exist with these elements in the first part. Add $a$ together with the second element in these pairs to $T$. In our case $e$ is related to $a$, $b, c, e$ hence we add $(a,a), (a,b), (a,c) $ and $(a,e)$ to T.
4. Repeat from step 3. for each new element found previously.
5. Repeat from step 1 for each element.

Note that after we have done up to step 5. for $a$ T will consist of $\{(a,a),(a,b),(a,c),(a,d),(a,e)\}$

This method is essentially to write the graph which R forms, and see which elements you may reach from each node, and add these edges to the graph, why you may call it the connectivity relation.