5
$\begingroup$

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

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

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

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

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.

| cite | improve this answer | | | | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – John Wayland Bales Nov 14 '18 at 5:00
  • $\begingroup$ @John Wayland Bales Corrected. Thanks ! $\endgroup$ – Jean Marie Nov 14 '18 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.