If I have a certain relation R, how do I find R^2 and R^3?

Question

Suppose I have A = {a,b,c,d} and R = {(a,b),(b,c),(c,b),(c,d)}. How do I find R^2 and R^3?

Answer 1

At this point, you should be familiar with functions. If you know that $f(a)=b$ and you know that $f(b)=c$ you should know that $f^2(a)=f(f(a))=f(b)=c$. Composition of relations is just like composition of functions except that rather than always having one "output" for each input you could potentially have had many outputs and you need to keep track of each one.

You could picture this graphically as well... drawing a directed edge from one element to another if the first element is related to the second element. Think of it like a board game like snakes and ladders. The original relation, $R$, is the collection of all ways you can move from one point to another in a single turn. $R^2$ is the collection of all ways you can move from one point to another in exactly two turns. $R^n$ is the ways of moving from one point to another in exactly $n$ turns and so on...

So, you could go from $a$ to $c$ in two turns by taking the two individual steps $a\mapsto b\mapsto c$. You could go from $b$ back to $b$ in two turns as well taking the individual steps $b\mapsto c\mapsto b$, or from $b$ to $d$ in two turns taking the steps $b\mapsto c\mapsto d$. See if you can find any other paths you could take over two turns and then see if you can find all ways you could go somewhere in three turns.

If you are well organized and can spot things like this quickly and easily, just going through by inspection can be just fine and may be the most efficient way to approach the problem. If the problem is much larger, convoluted, or if you just want a more formal generic approach that doesn't rely on inspection, you may create an "adjacency matrix" $A$ for your relation. You may then calculate the adjacency matrix for $R^n$ by simply computing the matrix $A^n$, keeping all zero entries as zero and replacing all nonzero entries with $1$, making such replacements in inbetween steps during calculations as well if desired. (Not replacing the nonzero entries can be of interest though as those numbers can tell you "how many different ways you could get from one point to another in that number of steps)

Here, we have the adjacency matrix (a matrix where the $i$'th row $j$'th column entry is $1$ if the $i$'th element is related to the $j$'th element in our set according to our relation):

$$A=\begin{bmatrix}0&1&0&0\\0&0&1&0\\0&1&0&1\\0&0&0&0\end{bmatrix}$$

We can then calculate $A^2$ and $A^3$ and interpret as the adjacency matrices of $R^2$ and $R^3$ respectively.

$R^2 = \{(a,c),(b,b),(b,d),(c,c)\}$, $R^3 = \{(a,b),(a,d),(b,c),(c,b),(c,d)\}$