Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Gerry Myerson Feb 25 '12 at 2:24
    
@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!!! –  manuzhang Feb 25 '12 at 2:44

1 Answer 1

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.

share|improve this answer
    
So what do you think about the definition of RTC? –  manuzhang Feb 24 '12 at 4:37
    
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. –  Gerry Myerson Feb 24 '12 at 4:41
    
@manuzhang: The definition is fine if the author’s definition of path allows paths of length $0$. –  Brian M. Scott Feb 24 '12 at 11:48
1  
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". –  Gerry Myerson Feb 24 '12 at 22:46
1  
@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. –  Brian M. Scott Feb 25 '12 at 0:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.