Powers of a Relation

Topics: Discrete Mathematics - Relation

---

(definition)

Let $R$ be a relation on a set $A$. We define:

$$R^1=R$$

$$R^n=R\circ R^{n-1}$$

…where $\circ$ denotes relation composition.

Example

Let $A=\{1,2,3,4\}$ and $R=\{(1,2),(1,3),(2,4),(3,2)\}$.

We have that:

• $R\circ R=\{(1,4),(1,2),(3,4)\}$
• $R^3=R\circ R^2=\{(1,4)\}$

…and that:

• $R^n=\varnothing$ for $n\ge 4$