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.
Best Answer
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.