Finding $R \circ S$, $S \circ R$, and $R \circ R$ for given relations $R,S$

26.7k Views Asked by At

For the following relations on $\{1,2,3,4,5,6,7,8,9,10\}$.

$R=\{(1,2),(3,6),(4,1),(5,5),(6,4),(7,5)\}$

$S=\{(2,1),(3,6),(9,4)\}$

What I got:

$R∘S = \{(2,2),(3,4),(9,1)\}$

$S∘R = \{(1,1)\}$

$R∘R = \{(3,4),(4,2),(5,5),(6,1),(7,5)\}$

The question stated that "If it is not possible to determine the relation then explain the reason." So I would like to ask is there are any answer not to possible to determine the relation?

1

There are 1 best solutions below

0
On

$ \newcommand{\CC}{\mathcal{C}} $ Your work is correct. I would just like to suggest an approach that might help cement understanding of the topic of relation composition where possible, and develop and intuition for it (and in particular see analogies to function composition since, after all, functions are fundamentally relations).

Personally, when possible, I like to approach this sort of problem visually. Write out the elements of the relevant set, in columns, four times over. (For convenience, I will also label the columns $\mathcal C_i$, for $i=1,2,3,4$.) Then, in the gaps between $\CC_1$ and $\CC_2$, draw arrows between the two, where $x$ in $\CC_1$ points to $y$ in $\CC_2$ if and only if $(x,y) \in R$. Replicate this exactly for the gap between $\CC_3$ and $\CC_4$. Finally, draw arrows similarly in the gap for $\CC_2$ and $\CC_3$ representing the relation $S$: $x$ in $\CC_2$ points to $y$ in $\CC_3$ if and only if $(x,y) \in S$.

The diagram you should get is something like this:

enter image description here

You might be guessing what comes next. Essentially, if $x$ in $\CC_1$ points to $y$ in $\CC_2$, and then to $z$ in $\CC_3$, then $(x,z) \in S \circ R$. Or put differently: if there is a path from $x$ in $\CC_1$ to $z$ in $\CC_3$ you can walk along, then $(x,z) \in S \circ R$.

Similarly, the existence of such a path for $x$ in $\CC_2$ to $z$ in $\CC_4$ gives $(x,z) \in R \circ S$.

It will usually be easiest to just start in $\CC_3$, and see if you can trace backwards to $\CC_1$ (and similar for $\CC_4$ and $\CC_2$), but that's up to you. Anyhow, with this in mind, it becomes clear that

$$R \circ S = \{(2,2),(3,4),(9,1)\} \qquad S\circ R = \{(1,1)\}$$

after all.

A similar idea can be used for $R \circ R$. Make three columns with your elements, and in each gap between the columns, draw lines representing the relation $R$. (I drew the bolded lines to indicate the relevant bits of the relation.)

enter image description here

From this we easily see that

$$R \circ R = \left\{ (3,4), (4,2), (5,5), (6,1), (7,5) \right\}$$

as desired. And, of course, even though you didn't ask about that in particular, $S \circ S$ can also be found:

enter image description here

Namely, since no paths can be completed, $S \circ S = \varnothing$.


...granted, this question is quite old, so I imagine you don't need help now. But hopefully this helps someone in the future, and, if nothing else, gets this question out of the unanswered queue.