I need help with a transitive closure question

Question

the question deals with relations

$R$ is a binary relation defined on $A = \{0,1,2,3\}$.

Let $R = \{(0,1), (0,2), (1,1), (1,3), (2,2), (3,0)\}$.

Find $R^t$, the transitive closure of $R$.

I have the answer but I can't seem to figure out how to get to the answer. The answer: $\{(0,0), (0,1), (0,2), (0,3), (1,0), (1,1), (1,2), (1,3), (2,2), (3,0), (3,1), (3,2), (3,3)\}$

I dont understand the order of the points. For example, why is it (1,2) instead of (2,1)?

If anyone knows the steps or a website that can help with transitive closures, I would greatly appreciate it. Thanks!

Answer 1

Given a relation $R$ defined on some set $A = \{a_1,\ldots,a_n\}$, use the following algorithm to get the transitive closure:

For each k from 1 to n, do the following:
    For each i from 1 to n, do the following:
        For each j from 1 to n, do the following:
            If (a_i,a_k) and (a_k,a_j) are both in R, then do the following:
                Set R := R ∪ {(a_i,a_j)}.

This is a modified version of the Floyd–Warshall algorithm and has running time $O(n^3)$.

---

Note that if we run this algorithm on your given inputs, we would start by examining $a_1 = 0$. Since $(3,0) \in R$ and $(0,1),(0,2) \in R$, we would set $R:=R \cup \{(3,1),(3,2)\}$. This process repeats for each $a_k$.