2
$\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.

$\endgroup$
2
  • 1
    $\begingroup$ It seems to me that the Lewis and Rosen definitions disagree. A path $(a,b)$ would have length two by Lewis, one by Rosen. Well, every author is entitled to use his/her own definitions, so long as the definitions are stated clearly and applied consistently. I interpret Lewis as saying $(a)$ is a path of length one from $a$ to $a$, and the last sentence of your edit is in accord with Lewis' definitions. $\endgroup$ Feb 25, 2012 at 2:24
  • $\begingroup$ @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!!! $\endgroup$
    – manuzhang
    Feb 25, 2012 at 2:44

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ So what do you think about the definition of RTC? $\endgroup$
    – manuzhang
    Feb 24, 2012 at 4:37
  • $\begingroup$ Ah, yes. Well, if you've reported accurately what's in the book, then it appears that the author has stuffed it up. The definition defines TC, but the example exemplifies RTC. $\endgroup$ Feb 24, 2012 at 4:41
  • 1
    $\begingroup$ @manuzhang: The definition is fine if the author’s definition of path allows paths of length $0$. $\endgroup$ Feb 24, 2012 at 11:48
  • 2
    $\begingroup$ Start at $a$, go to $b$, then go to $c$ - that's a path of length two from $a$ to $c$. Start at $a$, go to $b$ - that's a path of length one from $a$ to $b$. Start at $a$, and don't go anywhere - that's a path of length zero from $a$ to $a$, provided your definitions allow such things. So I think it's time for you to have a look at how the author defines "path". $\endgroup$ Feb 24, 2012 at 22:46
  • 1
    $\begingroup$ @manuzhang: I didn’t see your comment, because you pinged me incorrectly: you have to use the first part of my name. Fortunately, Gerry saw it and has answered. $\endgroup$ Feb 25, 2012 at 0:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .