# Composition relation of R1 ∘ R2

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

• I must also be doing it wrong because I got what the answer is supposed to be except I got $(2,2)$ in addition. – John Wayland Bales Aug 6 '16 at 16:38

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

• Thanks allot! My tutor had wrote down the wrong answer by the looks of it, had this answer initially :) – user3768911 Aug 6 '16 at 17:00
• is there not another relation 5 -> 2 -> 5 for R2 o R1 given R1 has (5,2) and R2 has (5,5) – Rag Nov 13 '18 at 14:32
• @Rag Yes, you are correct. I will edit my answer. Thanks. – John Wayland Bales Nov 14 '18 at 4:46
• @JohnWaylandBales sir , isn't $2→5→5$ , also ? – ً ً Jun 7 '19 at 2:24
• @MithleshUpadhyay Yes, that is a second way to get $(2,5)$. – John Wayland Bales Jun 7 '19 at 18:24

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.

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

• Somehow we both missed the $(5,2)$ as pointed out by @Rag in the comment above. There should be a $1$ in row $5$ column $2$ in your product. – John Wayland Bales Nov 14 '18 at 5:00
• @John Wayland Bales Corrected. Thanks ! – Jean Marie Nov 14 '18 at 10:02