1
$\begingroup$

This a problem on the definition of reflexive transitive closure in Elements of the Theory of Computation(H.R.Lewis).

Definition 1.6.1: Let $R \subseteq A^2$ be a directed graph defined on a set $A$. The reflexive transitive closure of $R$ is the relation $R^* = \{ (a,b) : a, b \in A\text{ and there is a path from }a\text{ to }b\text{ in }R\}\;.$

Also, an example is given as $R = \{(a_1,a_2), (a_1,a_3), (a_1,a_4), (a_2,a_3), (a_3,a_4)\}$ and its reflexive transitive closure $R^* = \{(a_1,a_1), (a_1,a_2), (a_1,a_3), (a_1,a_4), (a_2,a_2), (a_2,a_3), (a_2,a_4), (a_3,a_3), (a_3,a_4), (a_4,a_4) \}\;.$

My doubt is whether the example goes with the definition and whether the definition is correct itself. By the definition, if $(a, b) \in R^*$ then there is a path from $a$ to $b$ in $R$. However, I can not find a path from $a_1$ to $a_1$ in $R$ but $(a_1,a_1) \in R^*$ as in the example.

I think what the definition wants to say is the transitive closure of $R$.

Edit: here's how the author defines path

A path in a binary relation $R$ is a sequence $(a_1, \ldots, a_n)$ for some $n \geq 1$ such that $(a_i, a_{i+1}) \in R$ for $i = 1, \ldots, n-1$; this path is said to be from $a_1$ to $a_n$. The length of a path $(a_1, \ldots, a_n)$ is $n$.

Although this doesn't seem to clear things up, I find the definition of path in directed graph in Discrete Mathematics and its Applications(Kenneth H.Rosen)

A path from $a$ to $b$ in the directed graph $G$ is a sequence of edges $(x_0,x_1), (x_1,x_2), (x_2,x_3), \ldots, (x_{n-1},x_n)$ in $G$, where $n$ is a nonnegative integer, and $x_0=a$ and $x_n=b$, that is, a sequence of edges where the terminal vertex of an edge is the same as the initial vertex in the next edge in the path. This path is denoted by $x_0, x_1, x_2, \ldots, x_{n-1}, x_n$ and has length $n$. We view the empty set of edges as a path from $a$ to $a$.

Thus, I was wrong about the length of $(a,a)$. It is of length 1 not 0. Moreover, the path denoted by just $x_0$ has length $0$. Since there is no edge of this path we view it from $a$ to $a$. It follows that $(a,a) \in R^*$ no matter whether $(a,a) \in R$ which satisfies the definition of reflexive transitive closure.

  • 0
    @GerryMyerson, well, so much about the definition stuff. I think I'm gonna stop here since I know which is TC and which is RTC and move on to some practical problems. Thanks for your help!!!2012-02-25

1 Answers 1

2

Reflexive transitive closure and transitive closure are different. The TC is the smallest transitive relation containing $R$; the RTC is the smallest reflexive transitive relation containing $R$. That's why $(a_1,a_1)$ is in the RTC, but not in the TC.

  • 0
    @Gerry: Thanks; I thought so, but I $w$asn’t sure.2012-02-25