Relation $R = \{(1,2), (2,2), (2,3), (3,2)\}$ is defined on $A = \{1,2,3\}$. Draw the digraph for the relation $R^3$.

Question

So I don't want an explicit answer, but I do need help getting it from $R^1 \rightarrow R^2 \rightarrow R^3$.

Relation $R = \{(1,2), (2,2), (2,3), (3,2)\}$ is defined on $A = \{1,2,3\}$. Draw the digraph for the relation $R^3$.

I've already created the digraph for the first, but just need a bit of a boost to get to the next few steps.

Answer 1

A pair $\langle a,b\rangle$ belongs to $R^2=R\circ R$ if there is an $x\in A$ such that $\langle a,x\rangle\in R$ and $\langle x,b\rangle\in R$. If $G$ is the digraph for $R$, that means that there’s an edge from $a$ to $x$ and another from $x$ to $b$. In other words, $\langle a,b\rangle\in R^2$ if there is a path of length $2$ in $G$ from $a$ to $b$.

For example, $\langle 1,2\rangle\in R$ and $\langle 2,3\rangle\in R$, so (taking $a=1,x=2,b=3$) we see that $\langle 1,3\rangle\in R^2$. Pictorially, we have the digraph $G$ shown below, which has a path of length $2$ from $1$ to $3$ by way of $2$.

What are the other paths of length $2$ in $G$?

• We can go from $1$ to $2$ and around the loop to $2$, so there’s a path of length $2$ from $1$ to $2$: $\langle 1,2\rangle\in R^2$.
• We can go from $2$ to $2$ to $2$ or from $2$ to $3$ to $2$, so there’s a path of length $2$ (two of them, in fact!) from $2$ to $2$, and $\langle 2,2\rangle\in R^2$.
• We can go from $2$ to $2$ to $3$, so $\langle 2,3\rangle\in R^2$.
• We can go from $3$ to $2$ to $2$, so $\langle 3,2\rangle\in R^2$.
• And finally, we can go from $3$ to $2$ to $3$, so $\langle 3,3\rangle\in R^2$.

Thus, $R^2=\{\langle 1,2\rangle,\langle 2,2\rangle,\langle 2,3\rangle,\langle 3,2\rangle,\langle 3,3\rangle\}$.

Now $\langle a,b\rangle\in R^3=R\circ R\circ R$ if and only if there are $x,y\in A$ such that $\langle a,x\rangle,\langle x,y\rangle$, and $\langle y,b\rangle$ are all in $R$. Alternatively, $R^3=R\circ R^2$, so $\langle a,b\rangle\in R^3$ if and only if there is an $x\in A$ such that $\langle a,x\rangle\in R$ and $\langle x,b\rangle\in R^2$. In graphical terms $\langle a,b\rangle\in R^3$ if and only if there is a path of length $3$ in $G$ from $a$ to $b$, or a path from $a$ to some $x$ in the digraph of $R^2$ and an edge from $x$ to $b$ in $G$. I’ll leave it to you to find all of those paths and thereby work out $R^3$.