Taking the closure of a relation

Consider the relation \(R \mathrel{\mathop:}=\left \{ \left \langle 1,2 \right \rangle, \left \langle 2,3 \right \rangle, \left \langle 3,4 \right \rangle \right \}\). We want to compute its transitive closure. We first add \(\left \langle 1,3 \right \rangle\) and \(\left \langle 2,4 \right \rangle\), which we can construct from the existing pairs via transitivity. But the result is still not transitive The relation now contains both \(\left \langle 1,3 \right \rangle\) and \(\left \langle 3,4 \right \rangle\), so we also have to add \(\left \langle 1,4 \right \rangle\). At this point, the relation is transitive, so we do not add any more edges.

Consider the relation \(R \mathrel{\mathop:}=\left \{ \left \langle 1,2 \right \rangle, \left \langle 3,2 \right \rangle \right \}\). Its transitive closure is just \(R\).

Consider once more the relation \(R \mathrel{\mathop:}=\left \{ \left \langle 1,2 \right \rangle, \left \langle 3,2 \right \rangle \right \}\). Now we want to compute its symmetric, transitive closure. As \(R\) is not symmetric, we have to add additional pairs, in this case \(\left \langle 2,1 \right \rangle\) and \(\left \langle 2,3 \right \rangle\). But \(R' \mathrel{\mathop:}=\left \{ \left \langle 1,2 \right \rangle, \left \langle 2,1 \right \rangle, \left \langle 2,3 \right \rangle, \left \langle 3,2 \right \rangle \right \}\) is not transitive. In order to make \(R'\) transitive, we have to add \(\left \langle 1,3 \right \rangle\) and \(\left \langle 3,1 \right \rangle\), but also \(\left \langle 1,1 \right \rangle\), \(\left \langle 2,2 \right \rangle\), and \(\left \langle 3,3 \right \rangle\). The resulting \(R'' \mathrel{\mathop:}=\left \{ 1,2,3 \right \} \times \left \{ 1,2,3 \right \}\) is transitive and symmetric, and even reflexive.