# What is $R\circ S$? For$s = \{(1,2),(1,3),(2,3),(2,4),(3,1)\}$ and … [closed]

Let $S = \{ (1,2), (1,3), (2,3), (2,4), (3,1) \}$ and $R = \{ (2,1), (3,1), (3,2), (4,2) \}$. Which of the following is $R \circ S$?

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

Working with this question. I think the last answer is the right one.

The scan of the original question can be found here.

## closed as off-topic by Andrés E. Caicedo, N. F. Taussig, Rory Daulton, Shailesh, Daniel W. FarlowFeb 24 '16 at 0:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Andrés E. Caicedo, N. F. Taussig, Rory Daulton, Shailesh, Daniel W. Farlow
If this question can be reworded to fit the rules in the help center, please edit the question.

• I think so too. – BrianO Feb 23 '16 at 15:59
• Do you know why? We are abit unsure in our group. – Martin Andersen Feb 23 '16 at 16:02
• Draw three tall ovals with numbers in each arranged in a column, the first of which representing the domain of $S$, the second of which representing the range of $S$ unioned with the domain of $R$, and the last representing the range of $R$. Draw arrows between numbers in the first oval and the second according to if that pair is in the relation $S$. Do so similarly for between the second and third oval according to the relation $R$. The composition of the relations corresponds to the length-two directed paths from the first oval to the third. – JMoravitz Feb 23 '16 at 16:14
• So the last option is the correct answer? – Martin Andersen Feb 23 '16 at 16:16
• same quesion – miracle173 Feb 23 '16 at 21:12

Using the relation $S$ you can get from $1$ to $2$ or to $3$, but not to anything else. Using the relation $R$, you can get from $2$ to $1$, and you can get from $3$ to $1$ or to $2$. Now put the pieces together:

\begin{align*} &1\overset{S}\longrightarrow 2\overset{R}\longrightarrow 1\\ &1\overset{S}\longrightarrow 3\overset{R}\longrightarrow 1\\ &1\overset{S}\longrightarrow 3\overset{R}\longrightarrow 2 \end{align*}\tag{1}

This says that the relation $R\circ S$ can get you from $1$ to $1$ and from $1$ to $2$, so $\langle 1,1\rangle$ and $\langle 1,2\rangle$ are in $R\circ S$. If you perform the same kind of analysis starting with $2$, you find that the possibilities are:

\begin{align*} &2\overset{S}\longrightarrow 3\overset{R}\longrightarrow 1\\ &2\overset{S}\longrightarrow 3\overset{R}\longrightarrow 2\\ &2\overset{S}\longrightarrow 4\overset{R}\longrightarrow 2 \end{align*}\tag{2}

This says that the relation $R\circ S$ can get you from $2$ to $1$ and from $2$ to $2$, so $\langle 2,1\rangle$ and $\langle 2,2\rangle$ are in $R\circ S$.

Starting from $3$, the relation $S$ can take you only to $1$, which isn’t an input to $R$ at all, so $R\circ S$ can’t take you anywhere: there are no pairs $\langle 3,x\rangle$ in $R\circ S$. And $4$ isn’t an input to $S$, so it isn’t an input to $R\circ S$, either, and there are no pairs $\langle 4,x\rangle$ in $R\circ S$. Thus,

$$R\circ S=\{\langle 1,1\rangle,\langle 1,2\rangle,\langle 2,1\rangle,\langle 2,2\rangle\}\;,$$

just as you thought.

Or you can follow the pictorial approach suggested by JMoravitz in the comments:

You’re looking for the paths from the leftmost copy of $\{1,2,3,4\}$ to the rightmost one, and you’ll find that there are exactly six of them, corresponding to $(1)$ and $(2)$ above.

Let $S = \{ (1,2), (1,3), (2,3), (2,4), (3,1) \}$ and $R = \{ (2,1), (3,1), (3,2), (4,2) \}$. Now, by definition, we have that $$R \circ S = \{ (x,z) \mid \exists y \colon (x,y) \in S \wedge (y,z) \in R \}.$$

Thus

• $(1,2) \in S \wedge (2,1) \in R \Rightarrow (1,1) \in R \circ S$,
• $(1,3) \in S \wedge (3,2) \in R \Rightarrow (1,2) \in R \circ S$,
• $(1,3) \in S \wedge (3,1) \in R \Rightarrow (1,1) \in R \circ S$,
• $(2,3) \in S \wedge (3,1) \in R \Rightarrow (2,1) \in R \circ S$,
• $(2,3) \in S \wedge (3,2) \in R \Rightarrow (2,2) \in R \circ S$ and
• $(2,4) \in S \wedge (4,2) \in R \Rightarrow (2,2) \in R \circ S$.

These are all the elements of $R \circ S$ and thus

$$R \circ S = \{(1,1),(1,2),(2,1),(2,2) \}.$$