[Math] Transitive Closure, $R =\{(0,0), (0,3), (1,0), (1,2), (2,0), (3,2)\}$

discrete mathematics

Let the relation $R = \{(0,0), (0,3), (1,0), (1,2), (2,0), (3,2)\}$
Find $R^*$ the transitive closure of $R$. Show all steps.

For the following problem I have a question on the Transitive Closure.
I know I have to add the following:
$\{(0,2), (1,3), (2,3), (3,0)\}$

Would I need $(1,1)$, $(2,2)$ and $(3,3)$, also to complete the transitive closure or would that be the reflexive closure? Also, am I missing any pairs?

Best Answer

A relation is transitive if whenever $x\sim y$ and $y\sim z$ then $x\sim z$.

Notice however, that if the relation is transitive and $x\sim y$, $y\sim z$ and $z\sim w$ as well, this further implies that $x\sim z$ and $z\sim w$ which implies that $x\sim w$.

When finding the transitive closure of a relation, you need to add all ordered pairs $(x,y)$ where you can write a sequence of pairs that already exist in the relation $(x,a_1),(a_1,a_2),\dots,(a_{n-1},a_n),(a_n,y)$ regardless of length.

In the relation above, you can write $2\mapsto 0\mapsto 3$, so you will need to add the pair $(2,3)$. You can also travel $2\mapsto 0\mapsto 3\mapsto 2$, so the pair $(2,2)$ will also need to be added.

Similarly for the others that you already found and $(3,3)$. However, the pair $(1,1)$ is not going to be added as there exist no pairs where $1$ is the second entry (nothing leads to it). As such, it doesn't cause any problem for the transitivity of the relation.

Related Question