Composition relation of R1 ∘ R2

Question

Let $R_1$ and $R_2$ be the relations on $\{1, 2, 3, 4, 5\}$ defined by

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

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

The answer for this is below but I'm not sure how they arrived at this answer.

Answer: $$R_2 \circ R_1 = \{(1,1),(2,3),(2,4),(2,5),(4,5),(5,5)\}$$

What I got: $$R_2 \circ R_1 = \{(1,1),(2,3),(2,4),(2,5),(2,2),(4,5),(5,5)\}$$

Answer 1

$$1\to1\to1$$ $$2\to2\to3$$ $$2\to2\to4$$ $$2\to3\to5$$ $$2\to5\to2$$ $$4\to3\to5$$ $$5\to5\to5$$

But, as pointed out by @Rag in the comments, there is one additional:

$$5\to5\to2$$

And, as pointed out by @MithleshUpadhyay, a second way to obtain $(2,5)$ is $$ 2\to5\to5$$

Answer 2

Here is how to think about RoS: (not a definition, just a way to think about it.) You have a subway system with stations {1,2,3,4,5}. It is served by the R-line and the S-line. (This is much simpler than NYC, where we old-timers can't find the BMT any more.) But the rules of travel are bit confining. You must first take the S line one stop, transfer to the R-line and go one stop. If you can start at a and get to b under these rules of travel, (a,b) belongs to RoS. Otherwise it doesn't. Take R={(1,1),(2,2), (2,4),(2,5),(4,3), (5,5)} and S to be your first relation. Let's start at 2. You could take the S-train from 2 to 3, but unfortunately 3 is not served by the R-line, and the rules are that you must take the R-line one stop. But there is still hope, you can take the S-line from 2 to 4 and then take the R-line from 4 to 3. Thus, the one pair belonging to RoS is (2,3). The answer to the obvious question, why is RoS defined backwards to mean you must first take the R-line and then take the S-line, is that the crazy analysts got there first and defined the composition of two functions fog, to mean first "do" g and then "do" f.

Answer 3

An alternative is through matrix representations of relations ($a_{ij}=1$ if $(i,j)$ is present in the relation, $0$ otherwise) with composition of relations replaced by matrix product (in the same order as in the composition, with boolean addition convention: $1+1=1$). This can be very useful on a computer. Here, we have :

$$\begin{pmatrix}1&0&0&0&0\\0&1&1&0&1\\0&0&0&0&0\\0&0&1&0&0\\0&0&0&0&1\end{pmatrix} \times \begin{pmatrix}1&0&0&0&0\\0&0&1&1&0\\0&0&0&0&1\\0&0&0&0&0\\0&1&0&0&1\end{pmatrix}=\begin{pmatrix}1&0&0&0&0\\0&1&1&1&1\\0&0&0&0&0\\0&0&0&0&1\\0&1&0&0&1\end{pmatrix}$$