Power of a relation ($R^n$)

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,\dots ,x_n=b$ has $x_{i-1}R{x}_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\ge 1}{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.