Transitive closure of a relation

Question

Having trouble answering the question.

Let $A=\{1,2,3,4,5\}$ and $\mathcal{R}$ the relation on $A$ with matrix representation:

$$\begin{array}{c|ccccc} &1&2&3&4&5\\ \hline 1&T&F&F&F&F\\ 2&F&T&F&T&F\\ 3&F&F&T&F&F\\ 4&F&T&F&T&T\\ 5&F&F&F&T&T\end{array}$$

(i): Determine the transitive closure $\mathcal{R}^*$ of $\mathcal{R}$. Express your answer as a set of ordered pairs.

(ii): Write down the partition of the set $A$ into equivalence classes induced by $\mathcal{R}^*$.

Thanks for help.

Answer 1

Hint:

Here is a directed graph representing the relation $\mathcal{R}$ with a directed edge from $x$ to $y$ iff $x\mathcal{R}y$.

Is it currently transitive?

Look at $2$ and $5$. You have $2\mathcal{R}4$ and you have $4\mathcal{R}5$ but...

What is the necessary edge(s) you need to make it transitive?

By adding those necessary missing edges to the graph (equivalently to the relation) you form $\mathcal{R}^*$. Remember, only add the edges you absolutely need to, don't add more than is necessary.

Is there a natural way to partition these elements so that in the image they are "grouped" how the edges appear?