0
$\begingroup$

Let $R\subset A\times A$ a binary relation, and note $a\sim b$ for $(a,b)\in R$. We define

$$(a,b)\in R\circ R\Leftrightarrow \exists b\in A : a\sim b, b\sim c$$

and $R^n=R\circ\dots\circ R$.

My books says that $(a,b)\in R^n$ iff there is a path of length $n$ in the graph of $R$. Isn't it false ?

For example, if $(a,b)\in R^3$, there exists $c\in A$ such that $(a,c)\in R^2$, $(c,b)\in R^2$ $\Leftrightarrow$ there exists $d, f\in A$ such that $$a\sim d\sim c\sim f\sim b$$ which is a path of length 4, not 3.

1 Answers 1

2

Your book is right. Note that $R^3 = R \circ R \circ R = R^2 \circ R$, not $R^2 \circ R^2$.

  • 0
    Thank you, sorry for the confusion :)2010-11-07