How do you find $R^2$ and $R^3$ and $R\circ T$?

Question

Given relations $R$ and $T$ on $\{a,b,c,d,e\}$

where $R = \{(a,b), (a,e), (b,c), (c,e), (e,e)\}$

where $T = \{(a,d), (d,e), (e,a)\}$

I don't have an equation, so how do I find $R^2$ and $R^3$ and $R\circ T$?

Answer 1

Using matrix multiplication:

$(a,b),(a,e),(b,c),(c,e),(e,e)$

(For $R^2$) Take the matrix $$M_R = \begin{matrix} 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}$$

Then $$M_R^2 = \begin{matrix} 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \end{matrix}$$

And hence you can read $R^2$ off $M_R^2$ as $$ R^2 = \{ (a,c) , (a, e), (b,e), (c,e), (d,e), (e,e) \}$$

So, to answer your comment: yes, that's it.

Answer 2

Hint: Here is an equation for the composition: For relations $S, S' \subseteq \{a,b,c,d,e\}^2$ we have $$ S \circ S' = \{(x,y) \in \{a,b,c,d,e\}^2 \mid \exists z: (x,z)\in S', (z,y) \in S\} $$ Now check for each pair if you can find a $z$. And $R^2 = R\circ R$, $R^3 = R \circ R^2$.