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

Question

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 :-)

Answer 1

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?

Answer 2

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\}$$

Answer 3

I wanna introduce the domain and the range of $R$, which are defined in Elements of Set Theory by Herbert B. Enderton:

\begin{align} x \in \mathrm{dom} R &\Leftrightarrow \exists y :\: \left( x,\, y \right) \in R,\\ x \in \mathrm{ran} R &\Leftrightarrow \exists t :\: \left( t,\, y \right) \in R. \end{align}

It'll help you think.

---

Because $ R = \left\{ \left(1,\,3\right),\;\left(1,\,5\right),\;\left(2,\,3\right),\;\left(2,\,5\right),\;\left(3,\,5\right),\;\left(4,\,5\right) \right\} $.

We can get $\mathrm{dom} R = A = \left\{1,\,2,\,3,\,4\right\}$, and $\mathrm{ran} R = \left\{3,\,5\right\}$.

To get $R \circ R$, evaluate $\mathrm{ran}R \cap \mathrm{dom}R = \left\{ 3,\, 5 \right\} \cap \left\{ 1,\, 2,\, 3,\, 4 \right\} = \left\{ 3 \right\}$, use the elements of it in the second $R$. It's obvious that the only possible routes are $1 \rightarrow 3 \rightarrow 5$ and $2 \rightarrow 3 \rightarrow 5$, i.e. $R \circ R = \left\{ \left(1,5 \right),\, \left( 2,\, 5 \right) \right\}$.

By definition, $R^{-1} = \left\{ (y,\,x) \mid xRy \right\}$. So $R^{-1} = \left\{ \left(3,\,1\right),\;\left(5,\,1\right),\;\left(3,\,2\right),\;\left(5,\,2\right),\;\left(5,\,3\right),\;\left(5,\,4\right) \right\} $. $\mathrm{dom}R^{-1} = \mathrm{ran}R = \left\{ 3,\,5 \right\}$.

Similarly, to get $R \circ R^{-1}$, evaluate $\mathrm{ran}R \cap \mathrm{dom}R^{-1} = \left\{ 3,\,5 \right\}$. Therefore we can get $R \circ R^{-1} = \left\{ \left(1,\,1\right),\;\left(2,\,2\right),\;\left(3,\,3\right),\;\left(4,\,4\right),\;\left(1,\,2\right),\;\left(2,\,1\right),\;\left(2,\,3\right),\;\left(3,\,2\right),\;\left(3,\,4\right),\;\left(4,\,3\right),\;\left(1,\,3\right),\;\left(3,\,1\right),\;\left(2,\,4\right),\;\left(4,\,2\right),\;\left(1,\,4\right),\;\left(4,\,1\right) \right\}$.