0
$\begingroup$

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$?

  • 0
    How can you find them? Well, you could calculate them explicitly by using the definition of composition.2012-11-29
  • 0
    what's the definition of composition?2012-11-29
  • 1
    You are trying to solve a problem without understanding it? That is never good.2012-11-29
  • 0
    isn't it for some z aRz ^ zRb, but how does that help me here?2012-11-29
  • 0
    wait do i need to do a matrix multiplication?2012-11-29
  • 0
    Matrices? Why would they have anything to do with this?2012-11-29
  • 1
    you can get the transitive closure by doing R o R n times as far as i can remember.2012-11-29
  • 0
    @mathnoob That's right. How about you write it up and post it as an answer?2012-11-29
  • 0
    ok so that's it?2012-11-29
  • 0
    i was asking how to find it, i didn't ask for answers.2012-11-29
  • 0
    Yep, that's it. I posted an answer.2012-11-29

2 Answers 2

0

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.

1

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$.

  • 0
    I can't find a z because I don;t have an equation.2012-11-29