Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
How can you find them? Well, you could calculate them explicitly by using the definition of composition. –  Asaf Karagila Nov 29 '12 at 16:31
    
what's the definition of composition? –  mathnoob Nov 29 '12 at 16:45
1  
You are trying to solve a problem without understanding it? That is never good. –  Asaf Karagila Nov 29 '12 at 17:36
    
isn't it for some z aRz ^ zRb, but how does that help me here? –  mathnoob Nov 29 '12 at 17:56
1  
you can get the transitive closure by doing R o R n times as far as i can remember. –  mathnoob Nov 29 '12 at 18:44

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
I can't find a z because I don;t have an equation. –  mathnoob Nov 29 '12 at 16:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.