Let the relation $R=\{(0,0),(0,3),(1,0),(1,2),(2,0),(3,2)\}$
Find the $R'$ the transitive closure of R.
I honestly don't understand this question at all. Am I being asked to first find $R'$ and then the transitive closure of $R$ given $R'$?
I'm not sure if my question makes sense, but appreciate any hints to solving this.
Best Answer
If $R,S$ are relations, then define $RS$ (or $R \circ S$) as $R \circ S = \{ (x,z) | \exists y \ xRy \text{ and } y S z\}$. Let $R^k$ be the composition of $R$ with itself $k$ times.
Then define $R^* = \cup_{k=1}^\infty R^k$. Since $R$ above is finite, then one can explicitly compute $R^*$ in a finite number of steps by a 'fixed point' computation starting with $R$.
By 'fixed point', I mean to find the smallest set $Q$ such that $R \subset Q$ and $RQ \subset Q$, and the scheme is $Q_0 = R$, $Q_{k+1}= Q_k \cup R Q_k$, stopping when $Q_{k+1} = Q_k$.