# To find $R\circ R^{-1}$ in Discrete mathematics

Today I came across a question in DMS which says:

If $R$ is the relation “Less Than” from $A = \{1, 2, 3, 4\}$ to $B = \{1,3,5\}$ then find $R\circ R^{-1}$.

Now what is $R\circ R^{-1}$?

I know how to find $R\circ R$, like in this question firstly we will find $R$ where

$$R= \{(1,3),(1,5),(2,3),(2,5),(3,5),(4,5)\}$$

and then $R\circ R$ would be:

$$\{(1,5),(2,5),(3,5),(4,5)\}.$$

Please correct me if I'm wrong. And also please explain how to find $R\circ R^{- 1}$? Thanks in advance :-)

• why do you think that RoR is {(1,5),(2,5),(3,5),(4,5)} ? I thought it would be {(1,5),(2,5)} ? – Nils Ziehn Jan 11 '14 at 19:07
• @ Nils Ziehn , please explain . – Gaurang Tandon Jan 11 '14 at 19:08
• I edited towards legibility and hope I matched what was intended – Hagen von Eitzen Jan 11 '14 at 19:11
• After executing $R$ once, you are either at $3,4 or 5$ and when you then execute $R$ again, you have to go from $3, 4 or 5$, but from $4$ and $5$ you have nowhere to go, right? Therefore you can only chose the ones that lead to $3$, which are $1$ and $2$ for a starting point and will both lead to $5$ at the end – Nils Ziehn Jan 11 '14 at 19:13
• If you are familiar with relation matrix , write that relation matrix named by M,then find M*M ,then each element of matrix is not zero substitute by 1 , then write relation from matrix again ,it is RoR – Khosrotash Jan 11 '14 at 19:14

If $R\subseteq A\times B$, $S\subseteq B\times C$ are relations, then $S\circ R\subset A\times C$ is given by $$S\circ R=\{\,(a,c)\mid\exists b\in B\colon aRb\land bRc\,\}.$$ (So as a side remark, your example calculation of an $R\circ R$ is wrong, cf. Nils Ziehn's comment). Moreover $R^{-1}\subseteq B\times A$ is the reverse relation, given by $$R^{-1}=\{\,(b,a)\mid aRb\,\}.$$ Putting these togeher, $R\circ R^{-1}$ is a relation $\subseteq B\times B$ and specifically $$R\circ R^{-1}=\{\,(b_1,b_2)\mid\exists a\in A\colon a<b_1\land a<b_2\,\}.$$ Can you write that down explicitly?
I'm not 100% sure, but I think this is correct.. $$R\circ R=\{(1,5),(2,5)\}$$ therefore $$R\circ R^{-1}=\{(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)\}$$ or simpler $$R\circ R^{-1}=\{(a,b)|a,b \in 1,2,3,4\}$$