= Power of a relation
{title2=$R^n$}
= Relation power
{synonym}
For a <binary relation> $R$ on a <set> $A$, define $R^0=\{(a,a):a\in A\}$ and $R^{n+1}=R\circ R^n$ for nonnegative <integers> $n$, using <composition of relations>. A pair $(a,b)$ belongs to $R^n$ precisely when a sequence $a=x_0,x_1,\ldots,x_n=b$ has $x_{i-1}Rx_i$ for every $i$. This follows by <mathematical induction>, splitting off one step in the recurrence. Thus $R^n$ records paths with exactly $n$ steps, rather than at most $n$ steps. The <union> $\bigcup_{n\geq1}R^n$ is the <transitive closure of a relation>; including $R^0$ gives its <reflexive transitive closure>. The powers of a single relation agree under the two common composition-order conventions.
Back to article page
